Given a string s, xzz want to know how many different string a, where f(a,s) = i and length of a is n. f(a,s) means the longest length of |s1|, which string s1 is the substring of string a and the prefix of string s. xzz is lazy, so you need to tell him answer from i = 0 to i = |s|. xzz is kind, so string a and string s can only consist of the uppercase letter.
经典的kmp(或自动机)->转移图->转移矩阵->矩阵快速幂
First line of the input file contains an integer T(0 < T ≤ 100) that indicates how many cases of inputs are there.
The description of each case is given below:
The first line of each input case contains number n, m, n means the length of a and m means the length of s, n ≤ 10000000.
The second line of each input case contains string s, |s| ≤ 15.
The description of output for each test case is given below:
each case contains |s| + 1 lines.
The i-th line of the output for each test case contains number A, means numbers of different string a, where f(a,s) = i - 1.
The result is too big, so you only to print the result modulo 10^9 + 7.
1 2 2 AC
625 50 1