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: interview

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     # Initialize result 
  
    # Update x if it is more 
    # than or equal to p 
    x = x % mod  
  
    while (y > 0) : 
          
        # If y is odd, multiply 
        # x with result 
        if ((y & 1) == 1) : 
            res = (res * x) % mod 
  
        # y must be even now 
        y = y >> 1      # y = y/2 
        x = (x * x) % mod 
          
    return res 
      
  
# Driver Code 
  
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((n-k+1)*(26**(n-k)))%(10**9+7)
            print(((m+1)*power(26, m))%mod)

t=int(input())
def power(x, y) : 
    res = 1     # Initialize result 
  
    # Update x if it is more 
    # than or equal to p 
    x = x % mod  
  
    while (y > 0) : 
          
        # If y is odd, multiply 
        # x with result 
        if ((y & 1) == 1) : 
            res = (res * x) % mod 
  
        # y must be even now 
        y = y >> 1      # y = y/2 
        x = (x * x) % mod 
          
    return res 
      
  
# Driver Code 
  
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((n-k+1)*(26**(n-k)))%(10**9+7)
            print(((m+1)*power(26, m))%mod)
   



MOD=int(1e9+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)
			

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)