小 Mate 收到了一份父母送的礼物，是一个由英文小写字母组成的字符串 $S$。为了让这个聪明的礼物发挥点用处，他决定在写下一首歌时，用它来寻找押韵。

为了寻找特定的押韵，Mate 想要选择一个长度为 $D$ 且以字符序列 $XY$ 结尾的单词，即倒数第二个字母是 $X$，最后一个字母是 $Y$。Mate 选择单词的过程是：首先划掉给定序列中的一些字母，然后将未划掉的字母按原顺序拼接成一个单词。他想知道有多少种不同的划掉字母的方法，使得保留下来的单词满足上述条件。

如果划掉字母的位置集合不同，则认为两种选择单词的方式是不同的。

输入格式

输入的第一行包含一个由英文小写字母组成的字符串 $S$（$2 \le |S| \le 2000$）。

第二行包含一个整数 $Q$（$1 \le Q \le 500\,000$），表示 Mate 需要选择单词的押韵数量。

接下来的 $Q$ 行，每行包含一个整数 $D$（$2 \le D \le |S|$）和一个由两个英文小写字母组成的字符串 $XY$。

输出格式

输出共 $Q$ 行，第 $i$ 行输出满足第 $i$ 个押韵要求的方案数。由于方案数可能非常大，请输出其对 $1\,000\,000\,007$ 取模后的结果。

子任务

• 在占总分 40% 的测试数据中，满足 $|S| \le 50$。
• 在另外占总分 40% 的测试数据中，满足 $|S| \le 200$。

样例

输入样例 1

banana
3
2 na
3 ba
4 nn

输出样例 1

3
0
1

输入样例 2

malimateodmameitate
3
10 ot
7 aa
3 me

输出样例 2

2
464
56

说明

样例 1 解释：

长度为 2 且以 “na” 结尾的单词可以通过以下 3 种方式获得（划掉的字母用删除线表示）：

• ~~b~~ ~~a~~ ~~n~~ ~~a~~ n a
• ~~b~~ ~~a~~ n a ~~n~~ ~~a~~
• ~~b~~ ~~a~~ n ~~a~~ ~~n~~ a