她的名字
单测试点时限: 4.0 秒
内存限制: 512 MB
“他走过一个又一个星球，
却始终放不下对她的思念。“
”深情终究是一趟孤独的旅程，
她是他永远的牵绊。”

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

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

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

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

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

所以你想知道，她的名字能够组成多少个长度为 N 且结尾为数字 XY 的新词（如果从她名字中取出的任意一个数字位置不同，两个词就被认为是不同的）。
输入
第一行包含一个由数字构成的字符串 S (1≤|S|≤2 000)。

第二行包含一个整数 Q (1≤Q≤5⋅10^5)，表示需要选择的不同结尾数量。

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

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

答案可能会很大，你只需要输出对于 109+7 取模后的结果。

样例
input
312121
4
2 21
3 31
4 22
3 22
output
3
0
1
2
提示
样例中第一个询问：312121, 312121, 312121.

第二个询问：无。

第三个询问：312121.

#include<cstdio>
#include<cstring>
using namespace std;
char s[2005];
char x,y;
int n;
const int mod=1e9+7;
long long c[2005][2005];//记忆化搜索求组合数 
bool book[10][10];//xy这个结尾是否算过 
int num[10][10][2005];//xy以及x的下标 ，储存的是x后有几个y 
long long a[2005][10][10];//n,x,y结果 
bool booka[2005][10][10];//n,x,y是否算过 
long long f(int n,int m) {   //求组合数 
	if(c[n][m]) return c[n][m];
	if(n<m) return 0;
	if(n==m||m==0) return 1;
	if(n>m)
		return c[n][m]=(f(n-1,m-1)+f(n-1,m))%mod;
}
int main() {
	scanf("%s",s+1);
	int len=strlen(s+1);
	int Q;
	scanf("%d",&Q);
	while(Q--) {
		scanf("%d ",&n);
		scanf("%c%c",&x,&y);
		int ans=0;
		if(!book[x-'0'][y-'0']) {  //xy结尾没算过 
			for(int i=len; i>=1; i--) {
				if(s[i]==x)
					num[x-'0'][y-'0'][i]=ans;
				if(s[i]==y)
					ans++;
			}
			book[x-'0'][y-'0']=true;
		}
		long long sum=0;
		if(n<=len&&n>=2) {  //2<=n<=len才有解（也是为了防止数组越界） 
			if(!booka[n][x-'0'][y-'0']) {//n,x,y这组数据没算过 
				for(int i=1; i<=len; i++) {
					if(num[x-'0'][y-'0'][i]) {
						sum+=num[x-'0'][y-'0'][i]*f(i-1,n-2)%mod;//（x后y的数目）*（从这个x前面的数里抽n-2个数有多少种情况） 
						sum%=mod;
					}
				}
				a[n][x-'0'][y-'0']=sum;
				booka[n][x-'0'][y-'0']=true;
			} else
				sum=a[n][x-'0'][y-'0'];
		}
		printf("%lld\n",sum);
	}
	return 0;
}