問題文

冥界の音楽を司るオリオン君は冥界の住人のために$N$音からなる歌を作曲することになった。作曲には以下のような制約がある。

冥界の住人に聞こえる音は限られており、$1, 2, \dots, K$しかない。また、冥界の住人には同時に2つ以上の音が聞こえない。そのため、$i$番目の音を$T_i$とすると$1 \le T_i \le K$でなければならない。曲の始まりと終わりを示すため、最初と最後の音は$1$でなければならない。さらに、連続する3音の組み合わせのうち、冥界で許されるのは$M$種類だけである。具体的には、任意の連続する3音$T_i, T_{i+1}, T_{i+2}$に対し、$(T_i, T_{i+1}, T_{i+2}) = (P_j, Q_j, R_j)$となるような$j (1 \le j \le M)$が存在しなければならない。

上記の制約を満たす曲は何通りあるか求めよ。答えは非常に大きくなる可能性があるので、$10^9+7$で割った余りを出力せよ。

入力

$K\ M\ N$
$P_1\ Q_1\ R_1$
$P_2\ Q_2\ R_2$
$\dots$
$P_M\ Q_M\ R_M$

1行目に、使用できる音の種類$K$、許される進行の数$M$、音の数$N$がスペース区切りで与えられます。
その後$M$行、$P_i, Q_i, R_i$がスペース区切りで与えられます。

入力は全て整数
$1 \le K \le 6$
$1 \le M \le K^3$
$3 \le N \le 10^{18}$
$1 \le P_i, Q_i, R_i \le K$
$i \ne j$ならば$(P_i, Q_i, R_i) \ne (P_j, Q_j, R_j)$

出力

制約を満たす曲は何通りあるか、$10^9+7$で割った余りを出力してください。最後に改行してください。

サンプル

5 8 7
1 5 1
1 4 1
5 1 5
5 1 4
4 1 4
4 1 5
1 4 5
4 5 1

9

2 3 3
2 2 2
1 2 2
2 2 1

0

1 1 16
1 1 1

1