题目翻译
小伙伴从他那里得到了一系列英文字母的小写字母作为礼物 父母。 为了至少能对这么聪明的礼物有所用处，他决定将它用于 在写下一首歌时寻找韵律。
为了找到特定的韵律，Mate 想要选择一个长度为 D 且以数组结尾的单词 字符 XY，即倒数第二个字母是 X，最后一个是 Y。 Mate 的过程 选择一个单词是首先划掉给定序列中的一些字母，然后合并 他没有划掉的字母变成一个单词。 他想知道有多少不同 他可以划掉字母的方法，以便他满足给定的条件。
如果划掉的位置的集合，则认为两个词的选择是不同的 字母不同。
题目描述
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 crossed-out letters are different.
输入格式
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 ≤ 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.
输入的第一行包含一个英文字母 S (2 ≤ |S|) 的小写字母数组。 ≤ 2000)。
第二行输入包含整数 Q (1 ≤ Q ≤ 500 000)，不同的个数 Mate 需要选择单词的押韵。
以下 Q 行中的每一行都包含整数 D (2 ≤ D ≤ |S|) 和一个小写数组 来自任务的英文字母 XY 的字母。
输出格式
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.
样例 #1
样例输入 #1
banana
3
2 na
3 ba
4 nn样例输出 #1
3
0
1样例 #2
样例输入 #2
malimateodmameitate
3
10 ot
7 aa
3 me样例输出 #2
2
464
56提示
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:
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