考虑中第n个元素的状态，有两种情况
1.若选 ，则还需要前 个元素中选 个，在方案数为
2.若不选 ，则还需要前 个元素中选 个，方案数为
即=+
由于 , 固定,故可以预处理 的值，计算二位前缀和。
具体的: 表示 时有多少对 满足题意,则有：
在询问 时直接输出 即可
//组合数递推：
for(int i=0;i<=2000;i++){
f[i][0]=1;
}
for(int i=1;i<=2000;i++){
for(int j=1;j<=i;j++){
f[i][j]=f[i-1][j-1]+f[i-1][j];
f[i][j]%=k;
}
}
//前缀和：
for(int i=1;i<=2000;i++){
for(int j=1;j<=2000;j++){
S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1];
if(j<=i&&f[i][j]%k==0){
S[i][j]++;
}
}
}