/ 
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).