记录编号	606584	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]组合数问题	最终得分	100
用户昵称	梦那边的美好RE	是否通过	通过
代码语言	C++	运行时间	1.293 s
提交时间	2025-09-28 20:57:14	内存使用	47.87 MiB

#include <bits/stdc++.h>
using namespace std;
#define int long long
int t,n,m,k,c[2008][2008],ans[2008][2008];
void init(){
	c[0][0]=1;
	c[1][0]=c[1][1]=1;
	for(int i=2;i<=2000;i++){
		c[i][0]=1; 
		for(int j=1;j<=i;j++){
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
			ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
			if(c[i][j]==0){
				ans[i][j]++;
			} 
		}
		ans[i][i+1]=ans[i][i]; 
	}
}
signed main(){
	cin>>t>>k;
	init(); 
	while(t--){
		cin>>n>>m;
		if(n<m){
			cout<<ans[n][n]<<"\n";
		} 
		else{
			cout<<ans[n][m]<<"\n"; 
		}
	}
	
	return 0;
}