2 \(s / 128\) \(MB / 100\) points

Little Mate got an array of lowercase letters from the English alphabet as a present from his

parents. In order to have at least some use of such a 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 an array of

characters \(XY\) , i.e. where the next to last letter is \(X\) , and the last \(Y\) . Mate’s process of

selecting a word is by 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 so that he meets the given conditions.

The selection of two words is considered distinct if the sets of positions of the cross\(ed-ou\)t

letters are different.

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.

2 \(s / 128\) \(MB / 100\) points

The first line of input contains an array of lowercase letters of the English alphabet \(S\) (2 ≤| \(S\) |

≤ 2000).
The second line of input contains the integer \(Q\) (1 ≤ \(Q \le 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 an array of lowercase

letters of the English alphabet \(XY\) from the task.

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 .

생성자가 기록되지 않았습니다.

출처 COCI 2017/2018 Contest 6