Hitting the Targets

There are $N$ targets numbered from $1$ to $N$. The targets hang on $M$ strings. The $i$-th string has $A\_i$ targets hanging on it, and the sum of all $A\_i$ is $N$.

Seunghwan wants to hit all $N$ targets, hitting exactly one target per shot, using $N$ shots in total. Each time he shoots, he picks one string and hits the topmost or the bottommost target on that string. His arrow is a magic arrow, so a target that is hit disappears. If only one target remains on a string, that target is both the topmost and the bottommost one. If a string has no targets left, he does not pick that string. Count the number of orders in which Seunghwan can shoot the targets.

The first line contains the number of targets $N$ ($1\leq N\leq 5\times 10^6$) and the number of strings $M$ ($1\leq M\leq N$).

The second line contains the number of targets hanging on each string, $A\_1,A\_2,\cdots ,A\_M$ ($1\leq A\_i\leq N$; $\sum\_{i=1}^{M}A\_i=N$), separated by spaces.

Print the number of orders in which Seunghwan shoots the targets, modulo $10^9+7$, on the first line.

Note that $10^9+7$ is a prime number.