Problem Description

Given a string \( S \), there are \( Q \) queries. Each query specifies a number \( N \) and two characters \( A \) and \( B \). The task is to determine how many substrings of length \( N \) in \( S \) end with the characters \( A \) and \( B \), where \( A \) is the second-to-last character and \( B \) is the last character. Note that the selected letters do not have to be consecutive.

Problem Description

Little Mate received an array of lowercase letters from the English alphabet as a gift from his parents. To make use of this clever present, he decided to use it for finding rhymes when writing his next song.

To find a specific rhyme, Mate wants to select a word of length \( D \) that ends with the characters \( XY \), i.e., where the next-to-last letter is \( X \) and the last letter is \( Y \). Mate's process of selecting a word involves first crossing out some letters in a given sequence, and then merging the letters he didn't cross out into a single word. He wants to know in how many different ways he can cross out the letters to meet the given conditions.

The selection of two words is considered distinct if the sets of positions of the crossed-out letters are different.

Input Format

The first line of input contains a string \( S \) of lowercase letters from the English alphabet (2 ≤ |S| ≤ 2000).

The second line of input contains the integer \( Q \) (1 ≤ Q ≤ 500,000), the number of different rhymes for which Mate needs to select words.

Each of the following \( Q \) lines contains the integer \( D \) (2 ≤ D ≤ |S|) and a string \( XY \) from the task.

Output Format

The \( i \)-th out of \( Q \) lines must contain the required number of ways for the \( i \)-th rhyme. Since that number can be quite large, output only the value modulo 1,000,000,007.

Sample Input and Output

Sample Input #1

banana
3
2 na
3 ba
4 nn

Sample Output #1

3
0
1

Sample Input #2

malimateodmameitate
3
10 ot
7 aa
3 me

Sample Output #2

2
464
56

Notes

In test cases worth 40% of total points, it will hold |S| ≤ 50.

In test cases worth an additional 40% of total points, it will hold |S| ≤ 200.

Clarification of the first test case:

A word of length 2 that ends with "na" can be obtained in the following ways:

b a n a$\$n a​, b a$\$n a$\$​n a, b a$\$n​ a n$\$a

见题面 Input 部分

见题面 Output 部分