include
include <bits/stdc++.h>
using namespace std; struct tes { int a ; int b ; }; int n , m ; int t, k; int target =0 ; int MOD =1000000007; long long f[100000][2],s[100000]; tes test[100000] ; long long custom (long long n ) { if (n < 0 ) { return MOD + n ; } else return n ; } int main() { s[0] =0; freopen("474D.inp","r",stdin); freopen ("474D.out","w",stdout); cin >> t >> k ; for (int i=1 ; i <=t; i++) { cin >> test[i].a >> test [i].b ; target = max (target ,max (test[i].a,test[i].b)); } f[0][0] = 1; f[0][1] = 0; for (int i =1 ; i<=target ; i ++) { if (i<k) { f[i][0]=1 ; f[i][1]=0 ; s[i]=(s[i-1]+f[i][0] + f[i][1]) % MOD ; } else { f[i][0]=(f[i-1][0] +f[i-1][1]) %MOD ; f[i][1]= (f[i-k][0]+f[i-k][1]) % MOD ; s[i]=(s[i-1]+f[i][0] + f[i][1]) % MOD ; } } /* for (int j=0 ; j <= 1; j++) { for (int i=1 ; i <= target;i++) { cout << f[i][j] <<" "; } cout <<endl; }*/ for (int i =1 ; i<=t ; i++) { cout << custom(s[test[i].b]-s[test[i].a-1]) <<endl ; } return 0; }
//Can anybody help me , I can't figure out where the error come from , it runs alright on my machine
