32390번 - 과녁 맞히기

문제

번호가 1ドル$부터 $N$까지 적힌 $N$개의 과녁이 있다. 이 과녁들은 $M$개의 줄에 매달려 있다. $i$번째 줄에는 $A_i$개의 과녁이 매달려 있으며, $A_i$들의 합은 $N$이다.

승환이는 한 번에 한 개의 과녁을 정확히 맞혀서, 총 $N$번 활을 쏴 모든 과녁을 맞히려 한다. 활을 쏠 때마다 승환이는 줄을 하나 선택하고, 그 줄에서 가장 위 또는 가장 아래에 있는 과녁을 맞힐 것이다. 승환이의 화살은 마법의 화살이기 때문에 화살에 맞은 과녁은 사라진다. 줄에 과녁이 하나만 남아 있다면, 그 과녁은 맨 위 과녁이자 맨 아래 과녁이고, 줄에 과녁이 없다면 해당 줄은 선택하지 않는다. 이때, 승환이가 과녁을 쏘는 순서의 경우의 수를 구해보자.

입력

첫 번째 줄에 과녁의 개수 $N(1\leq N\leq 5\times 10^6)$과 줄의 개수 $M(1\leq M\leq N)$이 주어진다.

두 번째 줄에 각 줄에 매달린 과녁의 개수 $A_1,A_2,\cdots ,A_M(1\leq A_i\leq N;$ $\sum_{i=1}^{M}A_i=N)$이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 승환이가 과녁을 쏘는 순서의 경우의 수를 10ドル^9+7$로 나눈 나머지를 출력한다.

단, 10ドル^9+7$은 소수이다.

제한

힌트