Mr. D はカードゲームで勝負をすることになった。 このカードゲームでは、 N 枚のカードの山を用いる。 また、山のカードには、上から順に 1, 2, 3, ... , N の番号がついている。
D で始まるものすべてを背負う彼に敗北は許されないが、不幸にも Mr. D はカードゲームが不得手である。 そこで、自分が引くカードをコントロールすることで勝利を手にすることにした。
Mr. D は K 種類のシャッフルが可能である。 K 種類のうち i 番目のシャッフルでは上から a_i 枚目から a_i+b_i − 1枚目までのちょうど b_i 枚を引き抜き、上に重ねる。 i番目のシャッフルを1 回するとき、それぞれ t_i 秒を要する。
ちょうど T 秒のシャッフルの後、一番上のカードを C にする方法は何通りあるか。 数が多くなる可能性があるので、 10^9+7 で割った余りを出力せよ。
入力は次の形式で与えられる。
N K C T a_1 b_1 t_1 a_2 b_2 t_2 ... a_K b_K t_K
答えを 10^9+7 で割った余りを一行で出力せよ。
4 1 1 6 3 2 3
1
4 1 1 5 3 2 3
0
6 2 2 5 1 2 1 2 5 3
3
ちょうど 5 秒で一番上のカードを 2 にする方法は以下の 3 通りである。
1→1→2 1→2→1 2→1→1
6 8 3 10 1 4 5 1 3 3 1 6 5 1 2 2 1 1 4 2 5 1 4 3 1 2 1 3
3087