J - Color Ball /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : \(300\) 点

問題文

\(N\) 本の全て色が異なる筒があり、それぞれに筒と同じ色のボールが \(a_1\), \(a_2\), ..., \(a_N\)個入っています。全ての筒に入っているボールを合わせると \(M\) 個です。

筒の幅はボールちょうど1つ分です。空である筒はないものとします。

アヤコさんは次のような遊びを思いつきました。以下の条件を満たすように、筒からボールを出して入れ直すというものです。

  • 各筒に入っているボールの数が初期状態から変化していないこと。
  • 各筒に入っているボールの色は、その筒の色と異なること。

条件を満たすようなボールの入れ方は何通りあるでしょうか。\(10^9+7\) で割った余りを求めてください。

ただし、同色のボール同士の区別はしませんが、筒に入っているボールの色の順番を区別するものとします。

制約

  • \(1 \leq N \leq 2000\)
  • \(1 \leq M \leq 2000\)
  • \(1 \leq a_i \leq M\)
  • \(\sum a_i = M\)
  • 入力される値はすべて整数である。

入力

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

\(N\) \(M\)
\(a_1\) \(a_2\) \(\dots\) \(a_N\)

出力

問題の答えを1行に出力せよ。


入力例 1

2 4
2 2

出力例 1

1

条件を満たすのは2つのボールを下図のように入れ替えるパターンのみなので、答えは1通りです。

入力例 2

3 5
2 2 1

出力例 2

4

下図のように、答えは4通りです。

入力例 3

4 15
2 2 1 10

出力例 3

0

どのようにボールを入れても条件を満たすことができません。