前缀和

#include<bits/stdc++.h>
using namespace std;
int T,k,n,m;
int c[2005][2005];
int sum[2005][2005];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>T>>k;
//组合数求解
	for(int i=0;i<=2001;i++)
		for(int j=0;j<=i;j++)
			if(i==0||i==j)
				c[i][j]=1;
			else
				c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
//二维前缀和求解
	for(int i=1;i<=2001;i++)
		for(int j=1;j<=2001;j++)
			if(c[i][j]==0&&j<=i)//注意算组合数时满足j<=i
				sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+1;
			else
				sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
	while(T--)
	{
		cin>>n>>m;
		cout<<sum[n][m]<<"\n";
	}
	return 0;
}