N 羽のうさぎが長さ L−1 の平均台の上にいる。 i 番目のうさぎの初期位置は整数 x_iであり、 0 ≤ x_{i} \lt x_{i+1} ≤ L−1 を満たす。座標は右に進むほど大きくなる。任意の i 番目のうさぎは、任意の回数だけ、ちょうど距離 a_i だけ右方向にジャンプ(すなわち、x_i から x_i+a_i へ移動)することができる。ただし別のうさぎを飛び越えること、−1 以下または L 以上の位置に入ることはできない。また、同時にジャンプしていられるのは高々 1 羽であり、ある座標に存在できるうさぎの数も高々 1 羽である。
初期状態から始めてジャンプを任意の回数繰り返したあとの x_{0}, …, x_{N−1} の状態として、あり得るものは何通りあるか。1\,000\,000\,007 で割った余りで求めよ。
入力は以下の形式で与えられる。
N L
x_{0} … x_{N−1}
a_{0} … a_{N−1}
答えを1行で出力せよ。
1 3 0 1
3
1/0でうさぎがいる/いないを表現すれば、100, 010, 001 の 3 通りである。
2 4 0 1 1 2
4
1100, 1001, 0101, 0011 の 4 通りである。
10 50 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1
272278100
二項係数 C(50,10) = 10\,272\,278\,170 であり、それを 1\,000\,000\,007 で割ったあまりは 272\,278\,100 である。