Problem Description
光羽一点都不喜欢高代,某一次高代课上,光羽特意挑了最后一排的位置,睡着睡着,他忽然想到了这道字符串水题!
度度熊有k(k≥2)个序列s1,s2,..,sk,每个序列的长度均为n,且序列中每个数均是1到n之间某个整数,请问这k个串有多少个长度大于0的**公共子序列**?
解释:在每个序列中都选出一些位置,并将这些位置对应的字符**顺次**拼接起来,当它们都相等时,称其为公共子序列。
答案可能很大,请对109+7取模。
Input
第一行一个数,表示数据组数T。
每组数据第一行两个数k,n;接下来k行,每行一个长度为n的序列si。
数据组数T=80,分别有20组数据满足k=2,3,4,5。
每组数据均满足1≤n≤1000,**且s1,s2,...,sk中每一个数在1到n之间等概率随机生成!!**
随机生成!!
随机生成!!
随机生成!!
Output
每组数据输出一行,每行仅包含一个数,表示公共子序列个数。
Sample Input
4
2 3
1 2 1
2 3 1
3 3
1 2 3
2 3 1
1 2 3
4 3
3 2 2
3 1 3
2 3 1
3 2 1
5 3
3 1 3
3 1 1
1 2 3
2 3 3
1 3 3
Sample Output
4
4
2
8