Peter has a string s=s1s2...sn, let suffi =sisi+1...sn be the suffix starting with the i-th character of s. Peter knows m facts about the string s and the i-th fact is that the longest common prefix between suffxi and suffyi is li. (|xi - yi| ≤ k, where k is the given number.)
Now, Peter wants to know the number of strings containing lowercase English letters only which satisfy all the facts. The answer may be too large, just print it modulo 1000000007.
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains three integers n, m and k (1 ≤ n ≤ 100, 0 ≤ m ≤ 100, 1 ≤ k ≤ 8) -- the length of the string, the number of facts and the given number.
The next m lines, each contains three integers xi, yi, li (1 ≤ xi, yi ≤ n, 0 ≤ li ≤ n, max(xi, yi) + li - 1 ≤ n, |xi - yi| ≤ k).
Output
For each test case, output one integer denoting the answer. The answer must be printed modulo 1000000007.
Sample Input
2
2 0 2
3 1 2
1 2 1
Sample Output
676
650
