配点 : $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$

出力

答えを出力せよ。

3 2
3 2

12

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

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

337587117

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