The year is 2136. A lot of things have changed but BITS Pilani still exists. The display technology used now is a WASDLED screen.

This display technology consists of a configuration matrix containing a row of N cells each of which can display K different symbols. These K symbols are partitioned into sets X1, X2, ... , Xm

The potency of a configuration matrix is the highest integer i, 1 <= i <= m, such that there is a symbol from Xi in some cell. The configurations with odd potency are invalid whereas those with even potency are valid.

The A3 and A8 students are obsessed with this new display technology. They wonder how many different valid configurations are possible. They turn to you for a solution. Since this number can be very large output this number modulo 1000000007.

Input

A single line containing the integers N and m as described above followed by a line containing m integers: X[1], X[2], ... , X[m] denoting the size (cardinality) of each set. Output

A single line containing the number of valid configurations. Constraints

1 <= N <= 1000000000 1 <= m <= 100000 1 <= X[i] <= 1000 Sample Inputs

Input: 3 2 2 2

Output: 56 Input: 2 3 1 2 3

Output: 8