You will be given m strings. For each of those strings, you need to count the total number of appearances of that string as substrings in all possible strings of length n containing only lower case English letters.

A string may appear in a string multiple times. Also, these appearances may overlap. All these must be counted separately. For example, aa appears thrice in the string aaacaa: aaacaa, aaacaa and aaacaa.
Input

The first line contains one integer, T, the number of test cases. The description of each test case follows:
The first line of each test case will contain two integers n and m.
The ith of the next m lines will have one string in each line. All the strings will consist only of lower case English letters.

Output

For each test case, print “Case x:” (without quotes. x is the test case number, 1-indexed) in the first line.
Then print m lines. The ith line should contain the number of appearances of the ith string in all possible strings of length n. As the numbers can be very large, print the answers modulo 10^9+7
.

Constraints

1 ≤ T ≤ 100
1 ≤ n ≤ 100000
1 ≤ m ≤ 1000
1 ≤ Length of every string in input
1 ≤ Total length of all strings in one test case ≤ 5 * 105
1 ≤ Total length of all strings in one test file ≤ 5 * 106

Example

Input:
3
2 1
aa
2 1
d
12 3
cdmn
qweewef
qs

Output:
Case 1:
1
Case 2:
52
Case 3:
443568031
71288256
41317270

Explanation:

Testcase 1: aa is the only string of length 2 which contains aa as a substring. And it occurs only once. Hence the answer is 1.

你将得到m个字符串。对于这些字符串中的每一个，您需要将该字符串的外观总数作为所有可能的长度为n的字符串中的子串进行计数，这些字符串只包含小写字母。(百度翻译的不是很准，将就看吧）

1≤一个测试用例中所有字符串的总长度≤5*10^5

1≤一个测试文件中所有字符串的总长度≤5*10^6

反思：
1.没说所给字符串的长度<=n,所以数组不能开1e5+5,要开5e5+5（不然runtime error)
2.发现是26的j次方乘以26的k次方的和，然后就直接循环跑的，却忘了j+k是个定值，直接乘法就行

    //如此沙雕
    ll ans=0;
	for(int j=0,k=n-len;k>=0;j++,k--){
		ans+=(f(26,j)*f(26,k))%mod;
		ans%=mod;
	}

   //注意cnt要大于等于0
   int cnt=n-len;
   ll ans=(cnt+1)*f(26,cnt)%mod;

3.位运算快速幂不能用来求指数是负数的幂，不然会死循环（超时）(这道题那几发超时不是没记忆化的锅，嘤嘤嘤）

typedef long long ll;
ll f(ll a,ll b){
	ll B=b;
	ll s=1;
	while(b){
		printf("%lld\n",b);
		if(b&1){
			a%=mod;
			s%=mod;
			s*=a;
		}
		a%=mod;
		a*=a;
		b>>=1;
	}
}

总的来说就是写的有点急，还没分析完就下手写了（剁手嘤嘤嘤）

ac代码

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll c[500005];
char s[500005];
int main(){
	int T;
	scanf("%d",&T);
	c[0]=1;
	for(int i=1;i<500005;i++)
	c[i]=c[i-1]*26%mod;
	for(int Case=1;Case<=T;Case++){
		printf("Case %d:\n",Case);
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++){
			scanf("%s",s);
			int len=strlen(s);
			int cnt=n-len;
			if(cnt<0){
				printf("0\n");
				continue;
			}
			else if(cnt==0){
				printf("1\n");
				continue;
			}
			else{
				ll ans=(cnt+1)*c[cnt]%mod;
		      	printf("%lld\n",ans);
		    }
		}	
	}
	return 0;
}