EOJ Monthly 2018.12

C. 她的名字

单点时限: 4.0 sec

内存限制: 512 MB

“他走过一个又一个星球,
却始终放不下对她的思念。“
”深情终究是一趟孤独的旅程,
她是他永远的牵绊。”

我们每个人心中都有一只小狐狸。我们渴望被自己喜欢的人驯服。

爱情是彼此之间至为甜蜜的臣服。我们都是傻痴痴的小狐狸,徒具一副精明的外表。

就像你走到哪都挂念着她,想把她写进自己的歌里,成为你们共同的记忆。

你想从她全部由数字构成的名字里取出其中的 $N$ 个数字,维持原来的顺序,组成结尾为数字 $XY$ 的新词。

你自然希望自己的歌能够很长很长,歌词的每一句都能饱含甜蜜。

所以你想知道,她的名字能够组成多少个长度为 $N$ 且结尾为数字 $XY$ 的新词(如果从她名字中取出的任意一个数字位置不同,两个词就被认为是不同的)。

输入格式

第一行包含一个由数字构成的字符串 $S$ ($1 \le |S| \le 2~000$)。

第二行包含一个整数 $Q$ ($1\le Q\le 5 \cdot 10^5$),表示需要选择的不同结尾数量。

接下来的 $Q$ 行,每行包含了一个整数 $N$ ($1\le N\le 5 \cdot 10^5$) 和两个数字 $XY$,用空格隔开,表示需要选择的歌词的长度和结尾。

输出格式

对于每一个询问,输出一个整数,表示答案。

答案可能会很大,你只需要输出对于 $10^9+7$ 取模后的结果。

样例

Input
312121
4
2 21
3 31
4 22
3 22
Output
3
0
1
2

提示

样例中第一个询问:312121, 312121, 312121.

第二个询问:无。

第三个询问:312121.