007 - 平均台

問題文

N 匹のうさぎちゃんが長さ L − 1 の平均台の上にいます。 i 番目のうさぎちゃんの初期位置は整数 x_i であり、0 ≤ x_i < x_i+1 ≤ L − 1 を満たします。座標は右に進むほど大きくなります。

任意の i 番目のうさぎちゃんは、任意の回数だけ、ちょうど距離 a_i だけ右方向にジャンプ(すなわち、x_i から x_i + a_i へ移動)することができます。ただし別のうさぎちゃんを飛び越えること、−1 以下または L 以上の位置に入ることはできません。また、同時にジャンプしていられるのは高々 1 羽であり、ある座標に存在できるうさぎちゃんの数も高々 1 羽です。

初期状態から始めてジャンプを任意の回数繰り返したあとの x₀, …, x_N−1 の状態として、あり得るものは何通りあるでしょうか。1,000,000,007 で割った余りで求めてください。

入力

N L
x0 x1 ... xN−1
a0 a1 ... aN−1

1 行目にうさぎの匹数 N(1 ≤ N ≤ 5 000) ,平均台の長さ - 1 を示す L(N ≤ L ≤ 5 000) が与えられます。

2 行目にそれぞれのうさぎちゃんの初期位置 x_i(0 ≤ x_i < x_i+1 ≤ L − 1) が与えられます。

3 行目にそれぞれのうさぎちゃんがジャンプできる距離 a_i(0 ≤ a_i ≤ L − 1) が与えられます。

出力

答えを1行で出力してください。

入出力例

入力例 1

1 3
0
1

出力例 1

3

1 0 でうさぎちゃんがいる いないを表現すれば、100, 010, 001 の 3 通りである。

入力例2

2 4
0 1
1 2

出力例 2

4

1100, 1001, 0101, 0011 の 4 通りである。

入力例 3

10 50
0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 1

出力例 3

272278100

二項係数 C(50,10) = 10,272,278,170 であり、それを 1,000,000,007 で割ったあまりは 272,278,100 である。