单点时限: 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$ 取模后的结果。
312121 4 2 21 3 31 4 22 3 22
3 0 1 2
样例中第一个询问:312121, 312121, 312121.
第二个询问:无。
第三个询问:312121.