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 109+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.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print('Case ' + str(_ + 1) + ':')
	for i in range(m):
		s = input()
		ls = len(s)
		if ls > n:
			print('0')
		else:
			k = n - ls + 1
			print(k * pow(26, n - ls, 1000000007) % 1000000007)


MOD = 1000000007
for t in range(int(input())):
	print('Case ' + str(t + 1) + ':')
	(n, q) = map(int, input().split())
	for i in range(q):
		x = input().strip()
		xlen = len(x)
		if xlen > n:
			print(0)
			continue
		rem = n - xlen
		remtot = pow(26, rem, MOD)
		ans = remtot * (rem + 1) % MOD
		print(ans)


t = int(input())
for i in range(t):
	print('Case ', i + 1, ': ', sep='')
	inp = input().split()
	inp[0] = int(inp[0])
	inp[1] = int(inp[1])
	for j in range(inp[1]):
		length = len(input())
		if inp[0] == length:
			print('1')
		elif inp[0] < length:
			print('0')
		else:
			ans = (inp[0] - length + 1) * pow(26, inp[0] - length, 1000000007) % 1000000007
			print(ans)


t = int(input())

def power(x, y):
	res = 1
	x = x % mod
	while y > 0:
		if y & 1 == 1:
			res = res * x % mod
		y = y >> 1
		x = x * x % mod
	return res
for tc in range(t):
	(n, m1) = input().split()
	(n, m1) = (int(n), int(m1))
	print('Case ' + str(tc + 1) + ':')
	for i in range(m1):
		s = input()
		k = len(s)
		mod = 10 ** 9 + 7
		m = n - k
		if k > n:
			print(0)
		else:
			print((m + 1) * power(26, m) % mod)


MOD = int(1000000000.0 + 7)

def power(a, n):
	if n == 0:
		return 1
	if n == 1:
		return a
	x = power(a, n >> 1)
	x = x * x
	if x >= MOD:
		x %= MOD
	if n & 1:
		x = x * a
		if x >= MOD:
			x %= MOD
	return x
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	print('Case', _ + 1, end=':\n')
	for string in range(m):
		a = len(input())
		if a > n:
			print(0)
			continue
		print((n - a + 1) * power(26, n - a) % MOD)


t = int(input())
mod = 1000000007
for i in range(t):
	(n, m) = map(int, input().split())
	print('Case {:d}:'.format(i + 1))
	for j in range(m):
		arr = input()
		l = len(arr)
		if l > n:
			print(0)
		else:
			prod = pow(26, n - l, mod) * (n - l + 1)
			print(prod % mod)