After escaping the flying eggs and finding used candy, you decide to do some trick-or-treating yourself! Your neighborhood has ~N~ houses with ~M~ roads connecting them. You live in house ~1~ and want to travel along these roads to reach your friend's house ~N~. There are ~T~ types of candy and ~M~ roads, with each road ~i~ serving candy of type ~t_i~. For every road ~i~ that you traverse, you will receive one candy of type ~t_i~ . Since you don't want cavities, you want to reach your friend's house while collecting at most one of each type of candy. How many distinct paths can you take from house ~1~ to house ~N~ while satisfying this constraint?

A few important things to note:

• Since the answer can be quite large, please output the answer modulo ~10^9 + 7~.
• Your paths do not have to be simple (i.e. they may contain cycles).
• Once you reach house ~N~, you may not traverse any more edges.
• Two paths are different if for some ~i~, the ~i~^th edge on one path is different from the ~i~^th edge on the other.
• There may be multiple roads connecting the same pair of houses but no edge will connect the same house (e.g. ~u_i \neq v_i~ holds true).
• The graph is not guaranteed to be connected.

Constraints

In all test cases, ~2 \le N \le 18~, ~1 \le T \le 18~, ~1 \leq M \leq N^2~.

Note: You must solve all preceding subtasks in order to earn points for a specific subtask.

Subtask 1 [10%]

~N, T \leq 8~; in addition, the graph is guaranteed to form a tree (i.e. ~M = N - 1~, no cycles exist, and the graph is connected).

Subtask 2 [20%]

~N, T \leq 8~

Subtask 3 [70%]

No further constraints.

Input Specification

First line: ~N~, ~M~, and ~T~: the number of houses, number of roads, and number of candy types respectively.

Next ~M~ lines: ~u_i~, ~v_i~, and ~t_i~ (~1 \le u_i, v_i \le N~, ~u_i \neq v_i~, ~1 \le t_i \le T~), indicating a bidirectional road that connects houses ~u_i~ and ~v_i~ and serves candy of type ~t_i~.

Output Specification

One integer: the number of distinct paths you can take while satisfying the described constraint modulo ~10^9 + 7~.

Sample Input 1

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

Output for Sample Case 1

2

Explanation for Sample Case 1

See a diagram of the neighbourhood below:

The two ways to reach node ~N~ without receiving duplicate candies are

~1 \rightarrow 2 \rightarrow 5 \rightarrow 6~ and

~1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 6~.

Sample Input 2

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

Output for Sample Case 2

0

Explanation for Sample Case 2

There is no possible sequence of roads you can traverse without receiving duplicate candy.