Problem : 474D

DEANNOS

/*
::::
author:deannos_coder
::::
*/


#include "bits/stdc++.h"
using namespace std;
#define endl "\n"
#define mod 1000000007
#define ld long double
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define pll pair<ll, ll>
#define pii  pair<int, int>
#define ld  long double
#define ff  first
#define ss  second
#define vs  vector<string>
#define vpll vector<pll>
#define vb   vector<bool>
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()
#define gi greater<int> ()
#define srt(v) (sort(all())
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()
#define fo(i,n) for(ll i=0;i<n;i++)
#define Fo(i,k,n) for(ll i=k;i<n;i++)
#define min(a,b) (((a)<(b))?(a):(b))
#define MAXN 100005
const int N = int(3e5) + 99;
const int INF = int(1e9) + 99;
const int maxn = 2e5 + 100;
const int MAX = 200007;
ll dp[MAXN];
ll sum[MAXN];


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//int tt = 1;
	//cin >> tt;
	//while (tt--)
	//{
	int t, k;
	cin >> t >> k;
	dp[0] = 1;
	for (int i = 1; i < MAXN; i++)
	{
		if (i >= k)
		{
			dp[i] = (dp[i &mdash; 1] + dp[i &mdash; k]) % mod;
		}
		else
		{
			dp[i] = 1;
		}
	}
	for (int i = 1; i < MAXN; i++)
	{
		sum[i] = (dp[i] + sum[i &mdash; 1]) % mod;
	}
	while (t--)
	{
		int x, y;
		cin >> x >> y;
		ll ans = sum[y] &mdash; sum[x &mdash; 1];
		ans = (ans + mod) % mod;
		cout << ans << endl;
	}
	//}
	return 0;

}