Description

小 Mate 收到了一个由小写英文字母组成的数组，作为他父母送的礼物。为了让这个聪明的礼物有些用处，他决定在写下一首歌时用它来寻找押韵。

为了找到特定的韵脚，Mate 想要选择一个长度为 D 的单词，该单词以字符数组 XY 结尾，即倒数第二个字母是 X，最后一个字母是 Y。Mate 选择单词的过程是首先划掉给定序列中的一些字母，然后将未划掉的字母合并成一个单词。他想知道有多少种不同的方式可以划掉字母，以满足给定的条件。

如果两个单词的划掉字母的位置集合不同，则认为这两个单词是不同的。

Input Format

输入的第一行包含一个由小写英文字母组成的数组 S (2 ≤ |S| ≤ 2000)。

输入的第二行包含整数 Q (1 ≤ Q ≤ 500 000)，表示 Mate 需要选择单词的不同韵脚的数量。

接下来的 Q 行中的每一行包含一个整数 D (2 ≤ D ≤ |S|) 和一个由小写英文字母组成的字符数组 XY。

Output Format

Q 行中的第 $i$ 行必须包含第 $i$ 个韵脚所需的方式数。由于该数字可能非常大，只输出值对 1 000 000 007 取模后的结果。

banana
3
2 na
3 ba
4 nn

3
0
1

malimateodmameitate
3
10 ot
7 aa
3 me

2
464
56

Hint

在占总分 40% 的测试用例中，将满足 |S| ≤ 50。

在额外占总分 40% 的测试用例中，将满足 |S| ≤ 200。

第一个测试用例的说明：

以“na”结尾的长度为 2 的单词可以通过以下方式获得：

b a n a n a，b a n a n a，b a n a n a。

题面翻译由 ChatGPT-4o 提供。