Problem Statement

Orion, who presides over the music of the underworld, is going to compose a song consisting of $N$ notes for the residents of the underworld. The composition is subject to the following constraints.

The residents of the underworld can hear only a limited set of notes: $1, 2, \dots, K$. Also, they cannot hear two or more notes at the same time. Therefore, letting $T_i$ be the $i$-th note, $1 \le T_i \le K$ must hold. To mark the beginning and the end of the song, the first and last notes must be $1$. Furthermore, among combinations of three consecutive notes, only $M$ kinds are allowed in the underworld. Specifically, for any three consecutive notes $T_i, T_{i+1}, T_{i+2}$, there must exist a $j (1 \le j \le M)$ such that $(T_i, T_{i+1}, T_{i+2}) = (P_j, Q_j, R_j)$.

Find the number of songs satisfying the above constraints. Since the answer can be very large, output it modulo $10^9+7$.

Input

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

The first line contains the number of kinds of usable notes $K$, the number of allowed progressions $M$, and the number of notes $N$, separated by spaces.
Each of the following $M$ lines contains $P_i, Q_i, R_i$, separated by spaces.

All input values are integers.
$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$
If $i \ne j$, then $(P_i, Q_i, R_i) \ne (P_j, Q_j, R_j)$

Output

Output the number of songs satisfying the constraints, modulo $10^9+7$. Print a newline at the end.

Sample

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