問題文

\(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\)
• 入力される値はすべて整数である。

入力例 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

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