In math class, Bob is currently studying systems of linear equations. Being bored of his teacher's lectures, he decides to make a problem for himself. In his problem, he is trying to solve for the ~N~ variables, ~x_1,x_2,\dots,x_N~. He then writes ~M~ equations, the ~i~-th of which being the equation ~x_{a_i}+x_{b_i}=c_i~ where ~a_i \ne b_i~. Believing that simply finding a solution to this problem would be too easy, he instead wants to find how many solutions of ~(x_1,x_2,\dots,x_N)~ exist if he constrains each of the ~x_i~ to be a positive integer less than or equal to ~K~. Since this number might be very large, he would be satisfied with this number modulo ~10^9+7~.

Constraints

In all subtasks,
~2 \le N \le 300\,000~
~1 \le M \le 500\,000~
~1 \le K \le 10^9~
~1 \le a_i,b_i \le N~, ~a_i \ne b_i~
~2 \le c_i \le 2K~

Subtask 1 [10%]

~1 \le K \le 5~
~1 \le N \le 10~
~1 \le M \le 20~

Subtask 2 [20%]

There is at most ~1~ solution.

Subtask 3 [70%]

No additional constraints.

Input Specification

The first line contains three space-separated integers, ~N~, ~M~, and ~K~.
~M~ lines follow, the ~i~-th of which contains three space-separated integers, ~a_i~, ~b_i~, and ~c_i~.

Output Specification

Output one line containing one integer, the number of solutions ~(x_1,x_2,\dots,x_N)~ to the system modulo ~10^9+7~.

Sample Input 1

4 3 5
1 4 6
1 3 5
2 3 3

Sample Output 1

2

Explanation for Sample Output 1

The two solutions are ~(3,1,2,3)~ and ~(4,2,1,2)~.

Sample Input 2

4 4 5
1 2 2
1 3 2
1 4 2
2 4 4

Sample Output 2

0

Explanation for Sample Output 2

There are no solutions to this system of equations.