Problem Statement

Orion has decided to compose a choral piece. A chord progression that is too simple makes the piece boring, and one that is too complex makes it incomprehensible, so he wants a moderately complex chord progression. Here, a chord progression is defined as two consecutive chords. There are $300$ types of chords available, from chord $1$ to chord $300$, and there are $M$ types of chord progressions available. The $i (1 \le i \le M)$-th chord progression goes from chord $P_i$ to chord $Q_i (\ne P_i)$, and its complexity is $C_i$. Among the pieces formed by connecting $N$ chords, how many have a total complexity of exactly $K$? Since the answer can be very large, find the remainder when divided by $10^9+7$.

Input

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

All inputs are integers.
$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$
If $i \ne j$, then $(P_i, Q_i) \ne (P_j, Q_j)$
$0 \le C_i \le 300$

Output

Output the number of pieces whose total complexity is exactly $K$, modulo $10^9+7$. Print a newline at the end.

Sample

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