C - Cookie Distribution /

Time Limit: 2.525 sec / Memory Limit: 1024 MB

配点 : 800

問題文

N 人の子供たちがいます。子供たちには 1,2,\ldots,N と番号が振られています。 これから K 日間、子供たちにクッキーが配られることになりました。 i 日目には N 人の中から a_i 人の子供が等確率で選ばれ、選ばれた子供たちはそれぞれクッキーを 1 枚受け取ります。(K 回の子供の選択はすべて独立に行われます。)

K 日間で子供 i が受け取るクッキーの枚数を c_i として、子供たちの うれしさc_1 \times c_2 \times \ldots \times c_N で定義します。 うれしさの期待値に \binom{N}{a_1} \times \binom{N}{a_2} \times \ldots \times \binom{N}{a_K} をかけた値(これは整数となることが示せます)を 10^9+7 で割ったあまりを求めてください。

注記

\binom{n}{k} は異なる n 個の対象から k 個を選ぶ選び方の総数を表します。

制約

  • 1 \leq N \leq 1000
  • 1 \leq K \leq 20
  • 1 \leq a_i \leq N

入力

入力は以下の形式で標準入力から与えられる。

N K
a_1 a_2 \ldots a_K

出力

答えを出力せよ。


入力例 1

3 2
3 2

出力例 1

12
  • 1 日目では、子供 1,2,3 のいずれもクッキーを受け取ります。
  • 2 日目では、子供 1,2,3 のいずれか 1 人がクッキーを受け取りません。
  • どの場合もうれしさは 4 のため、うれしさの期待値は 4 となります。これに \binom{3}{3} \times \binom{3}{2} をかけた値である 12 を出力してください。

入力例 2

856 16
399 263 665 432 206 61 784 548 422 313 848 478 827 26 398 63

出力例 2

337587117
  • 期待値の \binom{N}{a_1} \times \binom{N}{a_2} \times \ldots \times \binom{N}{a_K} 倍を 10^9+7 で割ったあまりを求めてください。

Score : 800 points

Problem Statement

There are N children, numbered 1,2,\ldots,N. In the next K days, we will give them some cookies. In the i-th day, we will choose a_i children among the N with equal probability, and give one cookie to each child chosen. (We make these K choices independently.)

Let us define the happiness of the children as c_1 \times c_2 \times \ldots \times c_N, where c_i is the number of cookies received by Child i in the K days. Find the expected happiness multiplied by \binom{N}{a_1} \times \binom{N}{a_2} \times \ldots \times \binom{N}{a_K} (we can show that this value is an integer), modulo (10^{9}+7).

Notes

\binom{n}{k} denotes the number of possible choices of k objects out of given distinct n objects, disregarding order.

Constraints

  • 1 \leq N \leq 1000
  • 1 \leq K \leq 20
  • 1 \leq a_i \leq N

Input

Input is given from Standard Input in the following format:

N K
a_1 a_2 \ldots a_K

Output

Print the answer.


Sample Input 1

3 2
3 2

Sample Output 1

12
  • On the first day, all the children 1, 2, and 3 receive one cookie.
  • On the second day, two out of the three children 1, 2, and 3 receive one cookie.
  • Their happiness is 4 in any case, so the expected happiness is 4. Print this value multiplied by \binom{3}{3} \times \binom{3}{2}, which is 12.

Sample Input 2

856 16
399 263 665 432 206 61 784 548 422 313 848 478 827 26 398 63

Sample Output 2

337587117
  • Find the expected value multiplied by \binom{N}{a_1} \times \binom{N}{a_2} \times \ldots \times \binom{N}{a_K}, modulo (10^9+7).