問題文

オリオン君は合唱曲を作曲することにした。コード進行が簡単すぎると退屈な曲になり、複雑すぎると理解不能な曲になってしまうため、適度に複雑なコード進行になるようにしたい。ここではコード進行を連続するコード2つとする。利用できるコードはコード$1$からコード$300$までの$300$種類あり、利用できるコード進行は$M$種類ある。$i (1 \le i \le M)$番目のコード進行はコード$P_i$の次にコード$Q_i (\ne P_i)$に進む進行で、その複雑度は$C_i$である。コード$N$個をつなげた曲のうち、複雑度の合計がちょうど$K$になる曲は何通りあるか。答えは非常に大きくなる可能性があるので、$10^9+7$で割った余りを求めよ。

入力

$N\ M\ K$
$P_1\ Q_1\ C_1$
$P_2\ Q_2\ C_2$
$\dots$
$P_M\ Q_M\ C_M$

入力は全て整数
$2 \le N \le 300$
$1 \le M \le 300$
$0 \le K \le 300$
$1 \le P_i, Q_i \le 300$
$P_i \ne Q_i$
$i \ne j$ならば$(P_i, Q_i) \ne (P_j, Q_j)$
$0 \le C_i \le 300$

出力

複雑度の合計がちょうど$K$になる曲が何通りあるか、$10^9+7$で割った余りを出力してください。最後に改行してください。

サンプル

4 6 2
1 2 0
1 3 0
2 1 1
3 1 0
2 3 0
3 2 2

6

3 1 3
1 2 3

0