编程介的小学生 2017-05-04 12:43 采纳率: 20.3%
浏览 743
已采纳

LCP Array

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

  • 写回答

2条回答 默认 最新

  • threenewbee 2017-05-05 15:53
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 BP神经网络控制倒立摆
  • ¥20 要这个数学建模编程的代码 并且能完整允许出来结果 完整的过程和数据的结果
  • ¥15 html5+css和javascript有人可以帮吗?图片要怎么插入代码里面啊
  • ¥30 Unity接入微信SDK 无法开启摄像头
  • ¥20 有偿 写代码 要用特定的软件anaconda 里的jvpyter 用python3写
  • ¥20 cad图纸,chx-3六轴码垛机器人
  • ¥15 移动摄像头专网需要解vlan
  • ¥20 access多表提取相同字段数据并合并
  • ¥20 基于MSP430f5529的MPU6050驱动,求出欧拉角
  • ¥20 Java-Oj-桌布的计算