問題文
N 匹のうさぎちゃんが長さ L − 1 の平均台の上にいます。 i 番目のうさぎちゃんの初期位置は整数 xi であり、0 ≤ xi < xi+1 ≤ L − 1 を満たします。座標は右に進むほど大きくなります。
任意の i 番目のうさぎちゃんは、任意の回数だけ、ちょうど距離 ai だけ右方向にジャンプ(すなわち、xi から xi + ai へ移動)することができます。ただし別のうさぎちゃんを飛び越えること、−1 以下または L 以上の位置に入ることはできません。また、同時にジャンプしていられるのは高々 1 羽であり、ある座標に存在できるうさぎちゃんの数も高々 1 羽です。
初期状態から始めてジャンプを任意の回数繰り返したあとの x0, …, xN−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 行目にそれぞれのうさぎちゃんの初期位置 xi(0 ≤ xi < xi+1 ≤ L − 1) が与えられます。
3 行目にそれぞれのうさぎちゃんがジャンプできる距離 ai(0 ≤ ai ≤ 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 である。