daily 2

CF 474D

void solve(){
  int t,k;
  cin>>t>>k;
  vector<ll>dp(MAXN);
  vector<ll>sum(MAXN);
  dp[0]=1;
  for(int i=1;i<MAXN;++i){
    dp[i]=dp[i-1];
    if(i-k>=0){
        dp[i]=(dp[i]+dp[i-k])%MOD;
    }
    sum[i]=(sum[i-1]+dp[i])%MOD;
  }
  while(t--){
    int a,b;
    cin>>a>>b;
    cout<<(sum[b]-sum[a-1]+MOD)%MOD<<"\n";
  }
  return;
}