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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 't = int(input())\r\nfor i in range(t):\r\n  print(\'Case \', (i+1), ": ", sep=\'\')\r\n  inp = input().split()\r\n  inp[0] = int(inp[0])\r\n  inp[1] = int(inp[1])\r\n  for j in range(inp[1]):\r\n    length = len(input())\r\n    if inp[0] == length:\r\n      print("1")\r\n    elif inp[0] < length:\r\n      print("0")\r\n    else:\r\n      \r\n      ans = ((inp[0]-length+1)*(pow(26,inp[0]-length,1000000007)))%1000000007\r\n      print(ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13253