Funny String

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

你需要构造一个字符串使得这个字符串包含有你输入的m个长度相同的子串,
并且这m个子串在你构造的字符串中首次出现的顺序必须和输入顺序一致。
给定你需要构造的字符串长度n,
子串的个数m和m个子串的长度k。
请输出构造这样的字符串有多少种方式,答案对1e9+7取模。

(T<=5,n<=400,m<=20,k<=20)

Input

输入一个T,代表有T组数据。

输入n,m,k。

接下来有m行,每行包含一个长度为k的子串。

 

Output

输出格式见样例。

Sample Input

3
10 4 2
ab
ba
aa
bb
100 5 1
a
b
c
d
e
5 1 4
abab

Sample Output

Case 1: 6634780
Case 2: 132587252
Case 3: 52

Hint

Source

2018CCPC吉林站热身赛C题 by axuhongbo 搬运