3121: String addition

Give you a string X, only containing lowercase letters.

Give you m queries, each of which is : If the initial string is S, then add character  to the end of S randomly(with equal probability per character for each of the 26 characters) and ask the expectation of the number(added characters) that will keep the string being a substring of the string X.

The first line contains a number $n$($1\le n \le5*10^5$), which represents the length of the string X.

The second line contains a string, representing the string X.

The third line contains a number,$ m$$(1\le m\le 10^3)$, indicating the number of queries.

The next m lines, each containing a number and a string S, represent the length of the string S and the string.

It is guaranteed that the sum of length of s does not exceed $10^6$.

For each query, output the expectation mod $1000000007$.

5
ababa
4
4 abab
3 bab
2 ab
1 a

576923081
576923081
562983618
752422452