Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3934
LCP Array

Time Limit: 1 Second      Memory Limit: 65536 KB

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, yin, 0 ≤ lin, 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

Author: LIN, Xi
Source: The 16th Zhejiang University Programming Contest
Submit    Status