
ZOJ Problem Set  3934
Peter has a string s=s_{1}s_{2}...s_{n}, let suff_{i} =s_{i}s_{i+1}...s_{n} be the suffix starting with the ith character of s. Peter knows m facts about the string s and the ith fact is that the longest common prefix between suff_{xi} and suff_{yi} is l_{i}. (x_{i}  y_{i} ≤ 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. InputThere 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 x_{i}, y_{i}, l_{i} (1 ≤ x_{i}, y_{i} ≤ n, 0 ≤ l_{i} ≤ n, max(x_{i}, y_{i}) + l_{i}  1 ≤ n, x_{i}  y_{i} ≤ k). OutputFor each test case, output one integer denoting the answer. The answer must be printed modulo 1000000007. Sample Input2 2 0 2 3 1 2 1 2 1 Sample Output676 650 Author: LIN, Xi Source: The 16th Zhejiang University Programming Contest 