G: 運命力 - Destiny Draw -

問題

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

• N は整数で 2 \≤ N \≤ 40 を満たす。
• K は整数で 1 \≤ K \≤ \frac{N (N+1)}{2} を満たす
• C は整数で 1 \≤ C \≤ N を満たす
• T は整数で 1 \≤ T \≤ 1,000,000 を満たす
• a_i (i = 1, 2, ... , K) は整数で 1 \≤ a_i \≤ N を満たす
• b_i (i = 1, 2, ... , K) は整数で 1 \≤ b_i \≤ N − a_i + 1 を満たす
• a_i = a_j かつ b_i = b_j を満たすとき i = j に限定される
• t_i は整数で 1 \≤ t_i \≤ 5 を満たす

出力形式

答えを 10^9+7 で割った余りを一行で出力せよ。

入力例1

4 1 1 6
3 2 3

出力例1

1

入力例2

4 1 1 5
3 2 3

出力例2

0

入力例3

6 2 2 5
1 2 1
2 5 3

出力例3

3

ちょうど 5 秒で一番上のカードを 2 にする方法は以下の 3 通りである。

1→1→2
1→2→1
2→1→1

入力例4

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

出力例4

3087