递推前缀和（原理=杨辉三角）

#include<bits/stdc++.h>
using namespace std;
long long int c[2001][2001];
long long int ans[2001][2001];
int t,m;
int main(){
  cin>>t>>m;
  c[0][0]=1;
  for(int i=1;i<2001;i++){
    c[i][0]=1;
    for(int j=1;j<2001;j++){
      c[i][j]=(c[i-1][j-1]+c[i-1][j])%m;
      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];
  }
  while(t--){
    int a,b;
    cin>>a>>b;
    if(b>a)
      b=a;
    cout<<ans[a][b]<<endl;
  }
}