We saw the little game Marmot made for Mole's lunch. Now it's Marmot's dinner time and, as we all know, Marmot eats flowers. At every dinner he eats some red and white flowers. Therefore a dinner can be represented as a sequence of several flowers, some of them white and some of them red.

But, for a dinner to be tasty, there is a rule: Marmot wants to eat white flowers only in groups of size k.

Now Marmot wonders in how many ways he can eat between a and b flowers. As the number of ways could be very large, print it modulo 1000000007 (10^9 + 7).


-----Input-----

Input contains several test cases.

The first line contains two integers t and k (1 ≤ t, k ≤ 10^5), where t represents the number of test cases.

The next t lines contain two integers a_{i} and b_{i} (1 ≤ a_{i} ≤ b_{i} ≤ 10^5), describing the i-th test.


-----Output-----

Print t lines to the standard output. The i-th line should contain the number of ways in which Marmot can eat between a_{i} and b_{i} flowers at dinner modulo 1000000007 (10^9 + 7).


-----Examples-----
Input
3 2
1 3
2 3
4 4

Output
6
5
5



-----Note-----  For K = 2 and length 1 Marmot can eat (R).  For K = 2 and length 2 Marmot can eat (RR) and (WW).  For K = 2 and length 3 Marmot can eat (RRR), (RWW) and (WWR).  For K = 2 and length 4 Marmot can eat, for example, (WWWW) or (RWWR), but for example he can't eat (WWWR).

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Dynamic programming


Solutions:
(t, k) = map(int, input().split())
mod = 10 ** 9 + 7
arr = [0 for i in range(100001)]
arr[0] = 1
arr[1] = 1
if k == 1:
	arr[1] += 1
for i in range(2, len(arr)):
	if i >= k:
		arr[i] = (arr[i - 1] + arr[i - k]) % mod
	else:
		arr[i] = arr[i - 1] % mod
ans = [0 for i in range(100001)]
ans[1] = arr[1]
for i in range(2, len(arr)):
	ans[i] = (ans[i - 1] + arr[i]) % mod
for _ in range(t):
	(a, b) = map(int, input().split())
	print((ans[b] - ans[a - 1] + mod) % mod)


fib = []
summ = []
mod = 1000000007

def pre_calc(k):
	for i in range(100001):
		summ.append(0)
		fib.append(0)
	fib[0] = 1
	for i in range(1, 100001):
		fib[i] = fib[i - 1]
		if i >= k:
			fib[i] = (fib[i] % mod + fib[i - k] % mod) % mod
	for i in range(1, 100001):
		summ[i] = (summ[i - 1] % mod + fib[i] % mod) % mod

def solve():
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	pre_calc(k)
	for i in range(n):
		(l, r) = input().split()
		l = int(l)
		r = int(r)
		ans = summ[r] - summ[l - 1]
		while ans < 0:
			ans += mod
		print(ans)
solve()


import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7
(t, k) = list(map(int, input().split()))
a = []
max_ = 0
while t:
	t -= 1
	a.append(list(map(int, input().split())))
	max_ = max(max_, a[-1][1])
dp = [1] * (max_ + 1)
for i in range(k, max_ + 1):
	dp[i] = (dp[i - k] + dp[i - 1]) % MOD
for i in range(1, max_ + 1):
	dp[i] += dp[i - 1]
	dp[i] %= MOD
for (a_, b_) in a:
	print((dp[b_] - dp[a_ - 1]) % MOD)


def main():
	(t, k) = map(int, input().split())
	mod = 1000000007
	l = [1] * 100001
	for i in range(k, 100001):
		a = l[i - 1] + l[i - k]
		l[i] = a - mod if a >= mod else a
	for i in range(1, 100001):
		a = l[i] + l[i - 1]
		l[i] = a - mod if a >= mod else a
	res = []
	for _ in range(t):
		(a, b) = map(int, input().split())
		a = l[b] - l[a - 1]
		res.append(a + mod if a < 0 else a)
	print('\n'.join(map(str, res)))

def __starting_point():
	main()
__starting_point()


3
from sys import stdin, stdout
(t, k) = map(int, stdin.readline().split())
a = [0] * 100001
s = [0] * 100001
MOD = 1000000007
for i in range(0, 100001):
	if i < k:
		a[i] = 1
	else:
		a[i] = (a[i - 1] + a[i - k]) % MOD
	s[i] = (s[i - 1] + a[i]) % MOD
for i in range(0, t):
	(l, r) = map(int, stdin.readline().split())
	stdout.write(str((s[r] - s[l - 1] + MOD) % MOD) + '\n')


import sys, atexit, io
_INPUT_BUFFER = sys.stdin.readlines()
input = iter(_INPUT_BUFFER).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
M = 10 ** 9 + 7
(t, k) = map(int, input().split())
L = [tuple(map(int, input().split())) for i in range(t)]
ways = [0] * (1 + max(map(max, L)))
ways[0] = 1
for i in range(1, len(ways)):
	ways[i] = ways[i - 1] % M
	if i >= k:
		ways[i] = (ways[i] + ways[i - k]) % M
for i in range(1, len(ways)):
	ways[i] += ways[i - 1]
for (i, (a, b)) in enumerate(L):
	print((ways[b] - ways[a - 1]) % M)


import sys
import math as mt
input = sys.stdin.buffer.readline
mod = 10 ** 9 + 7
n = 10 ** 5 + 1
dp = [0] * n
(t, k) = map(int, input().split())
for i in range(n):
	if i >= k:
		dp[i] = (dp[i - k] % mod + dp[i - 1] % mod) % mod
	else:
		dp[i] = 1
for i in range(1, n):
	dp[i] = (dp[i - 1] % mod + dp[i] % mod) % mod
for __ in range(t):
	(a, b) = map(int, input().split())
	print((dp[b] - dp[a - 1]) % mod)


import sys
input = sys.stdin.readline
(t, k) = map(int, input().split())
nmax = int(100000.0 + 1)
mod = int(1000000000.0 + 7)
dp = [0 for i in range(nmax)]
dp[0] = 1
for i in range(1, nmax):
	if i >= k:
		dp[i] = (dp[i - 1] + dp[i - k]) % mod
	else:
		dp[i] = 1
for i in range(1, nmax):
	dp[i] += dp[i - 1]
	dp[i] %= mod
for _ in range(t):
	(a, b) = map(int, input().split())
	print((dp[b] - dp[a - 1] + mod) % mod)


import sys
(t, k) = (int(x) for x in sys.stdin.readline().split())
mod = 1000000007
l = [0] * 100001
l[0] = 1
for i in range(1, 100001):
	l[i] = (l[i - 1] + (l[i - k] if i - k >= 0 else 0)) % mod
for i in range(1, 100001):
	l[i] = (l[i] + l[i - 1]) % mod
for line in sys.stdin.readlines():
	(a, b) = (int(x) for x in line.split())
	print((l[b] - l[a - 1] + mod) % mod)


(t, k) = map(int, input().split())
n = 100001
dp = [[0] * 2 for i in range(n)]
mod = 10 ** 9 + 7
dp[0] = [1, 1]
for i in range(1, n):
	if i >= k:
		dp[i][1] += dp[i - k][0]
		dp[i][1] %= mod
	dp[i][0] += dp[i - 1][0]
	dp[i][0] %= mod
	if i - 1 >= k:
		dp[i][1] += dp[i - k][1]
		dp[i][1] %= mod
		dp[i][0] += dp[i - 1][1]
		dp[i][0] %= mod
pref = [0] * (n + 2)
for i in range(1, n):
	pref[i] = (pref[i - 1] + sum(dp[i])) % mod
for tt in range(t):
	(l, r) = map(int, input().split())
	print((pref[r] - pref[l - 1] + mod) % mod)


(t, k) = map(int, input().split())
m = 10 ** 9 + 7
dp = [x for x in range(1, k + 1)]
for i in range(k, 100001):
	dp.append((dp[i - 1] + dp[i - k] + 1) % m)
for i in range(t):
	(a, b) = map(int, input().split())
	print((dp[b] - dp[a - 1]) % m)


from math import ceil, sqrt
from collections import defaultdict
from itertools import permutations
(t, k) = map(int, input().split())
n = 10 ** 5 + 10
mod = 10 ** 9 + 7
dp = [0] * (n + k + 1)
dp[0] = 1
pre = [0] * (n + k + 1)
for i in range(1, n + 1 + k):
	dp[i] = dp[i - 1] + dp[i - k]
	dp[i] %= mod
	pre[i] = dp[i] + pre[i - 1]
for _ in range(t):
	(a, b) = map(int, input().split())
	print((pre[b] - pre[a - 1]) % mod)


import os
import sys
from io import BytesIO, IOBase
mod = 10 ** 9 + 7

def main():
	(t, k) = map(int, input().split())
	dp = [0] * (10 ** 5 + 1)
	for i in range(k):
		dp[i] = 1
	for i in range(k, 10 ** 5 + 1):
		dp[i] = (dp[i - 1] + dp[i - k]) % mod
	for i in range(1, 10 ** 5 + 1):
		dp[i] += dp[i - 1]
	for _ in range(t):
		(a, b) = map(int, input().split())
		print((dp[b] - dp[a - 1]) % mod)

def nouse0():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse1():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse2():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def nouse3():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse4():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse5():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
main()


3
MOD = 1000000007
(t, k) = map(int, input().split())
(a, b) = ([], [])
for i in range(t):
	(_a, _b) = map(int, input().split())
	a.append(_a)
	b.append(_b)
upper = max(b) + 1
way = [1]
sum_way = [1]
for i in range(1, upper):
	way.append((way[i - 1] + (way[i - k] if i >= k else 0)) % MOD)
	sum_way.append((sum_way[i - 1] + way[i]) % MOD)
for i in range(t):
	print((sum_way[b[i]] - sum_way[a[i] - 1]) % MOD)


(tests, tasty) = [int(n) for n in input().split()]
mod = 1000000007
menu = []
for i in range(0, 100001):
	if i < tasty:
		menu.append(1)
	else:
		menu.append((menu[i - 1] + menu[i - tasty]) % mod)
fullcourse = [1]
for i in range(1, len(menu)):
	fullcourse.append((fullcourse[i - 1] + menu[i]) % mod)
for i in range(tests):
	(minFlower, maxFlower) = [int(f) for f in input().split()]
	beethovenSnacks = (fullcourse[maxFlower] - fullcourse[minFlower - 1]) % mod
	print(beethovenSnacks)


import sys
import array

def solve():
	MOD = 1000000007
	size = 100003
	(t, groupsize) = read()
	mem = array.array('i', (0 for i in range(0, size)))
	summ = array.array('i', (0 for i in range(0, size)))
	mem[0] = 1
	for i in range(1, groupsize):
		mem[i] = mem[i - 1] % MOD
	for i in range(groupsize, len(mem)):
		mem[i] = (mem[i - 1] + mem[i - groupsize]) % MOD
	summ[0] = mem[0]
	for i in range(1, len(summ)):
		summ[i] = (mem[i] + summ[i - 1]) % MOD
	res = list()
	for i in range(t):
		(a, b) = read()
		res.append((summ[b] - summ[a - 1] + MOD) % MOD)
	return res

def read(mode=2):
	inputs = input().strip()
	if mode == 0:
		return inputs
	if mode == 1:
		return inputs.split()
	if mode == 2:
		return list(map(int, inputs.split()))

def write(s='\n'):
	if s is None:
		s = ''
	if isinstance(s, list):
		s = '\n'.join(map(str, s))
	if isinstance(s, tuple):
		s = ' '.join(map(str, s))
	s = str(s)
	print(s, end='')

def run():
	if sys.hexversion == 50594544:
		sys.stdin = open('test.txt')
	res = solve()
	write(res)
run()


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	(t, k) = LI()
	aa = [LI() for _ in range(t)]
	m = max(map(max, aa))
	c = [0] * (m + 1)
	for i in range(k):
		c[i] = 1
	for i in range(k, m + 1):
		c[i] = (c[i - k] + c[i - 1]) % mod
	d = [0] * (m + 1)
	d[0] = c[0]
	for i in range(1, m + 1):
		d[i] = (d[i - 1] + c[i]) % mod
	r = []
	for (a, b) in aa:
		r.append((d[b] - d[a - 1]) % mod)
	return '\n'.join(map(str, r))
print(main())


import sys
LI = lambda : list(map(int, sys.stdin.readline().strip('\n').split()))
MI = lambda : map(int, sys.stdin.readline().strip('\n').split())
SI = lambda : sys.stdin.readline().strip('\n')
II = lambda : int(sys.stdin.readline().strip('\n'))
(t, k) = MI()
(n, m) = (100001, int(1000000000.0 + 7))
dp = [0 for i in range(n)]
dp[0] = 1
for i in range(1, n):
	dp[i] = 1 if i < k else (dp[i - 1] + dp[i - k]) % m
for i in range(1, n):
	dp[i] = (dp[i] + dp[i - 1]) % m
for _ in range(t):
	(a, b) = MI()
	print((dp[b] - dp[a - 1] + m) % m)


import math
import bisect as bis
import heapq
M = 1000000007
(t, k) = map(int, input().split())
a = [0] * 100005
for i in range(k):
	a[i] = 1
for i in range(k, 100005):
	a[i] = (a[i - 1] + a[i - k]) % M
for i in range(1, 100005):
	a[i] += a[i - 1]
	a[i] %= M
for x in range(t):
	(a1, b1) = map(int, input().split())
	print((a[b1] - a[a1 - 1]) % M)


from itertools import accumulate as ac
(n, k) = map(int, input().split())
t = [0] + [1] * (k - 1) + [2]
m = 10 ** 9 + 7
for i in range(k + 1, 10 ** 5 + 2):
	t.append((t[-1] + t[-k]) % m)
t = list(ac(t))
for i in range(n):
	(a, b) = map(int, input().split())
	print((t[b] - t[a - 1]) % m)


import sys
input = sys.stdin.buffer.readline

def solution():
	m = 10 ** 9 + 7
	(t, k) = map(int, input().split())
	a = [1] * (10 ** 5 + 2)
	for i in range(k, len(a)):
		a[i] = (a[i - 1] + a[i - k]) % m
	for i in range(1, len(a)):
		a[i] = (a[i] + a[i - 1]) % m
	for _ in range(t):
		(x, y) = map(int, input().split())
		print((a[y] - a[x - 1]) % m)
solution()


from sys import stdin, stdout
inints = lambda : map(int, stdin.readline().split())
fastwrite = lambda s: stdout.write(str(s) + '\n')
irange = lambda x, y: range(x, y + 1)
modconst = 1000000007
(n, k) = inints()
f = [0] * 100001
ss = [0] * 100001
f[0] = 0
for i in range(1, k):
	f[i] = 1
f[k] = 2
for i in irange(k + 1, 100000):
	f[i] = (f[i - 1] + f[i - k]) % modconst
ss[0] = 0
for i in irange(1, 100000):
	ss[i] = (ss[i - 1] + f[i]) % modconst
for i in range(n):
	(a, b) = map(int, stdin.readline().split())
	fastwrite((ss[b] - ss[a - 1] + modconst) % modconst)


from __future__ import print_function
import math
from collections import deque
import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
(t, k) = invr()
s = [0] * (10 ** 5 + 1)
s[0] = 1
for i in range(1, 10 ** 5 + 1):
	if i - 1 >= 0:
		s[i] = (s[i - 1] + s[i]) % mod
	if i - k >= 0:
		s[i] = (s[i - k] + s[i]) % mod
ps = [0]
for i in range(10 ** 5 + 1):
	ps.append(ps[-1] + s[i])
for _ in range(t):
	(a, b) = invr()
	print((mod + ps[b + 1] % mod - ps[a] % mod) % mod)


(t, k) = map(int, input().split())
mod = 10 ** 9 + 7
N = 10 ** 5
res = [None] * (N + 1)
res[0] = 0
for i in range(1, k):
	res[i] = 1
res[k] = 2
for i in range(k + 1, N + 1):
	res[i] = (res[i - 1] + res[i - k]) % mod
for i in range(1, N + 1):
	res[i] += res[i - 1]
inputs = [map(int, input().split()) for _ in range(t)]
for (a, b) in inputs:
	print((res[b] - res[a - 1]) % mod)


(t, k) = map(int, input().split())
mod = 1000000007
res = [x for x in range(1, k + 1)]
for i in range(k, 100001):
	res.append((res[i - 1] + res[i - k] + 1) % mod)
for _ in range(t):
	(a, b) = map(int, input().split())
	print(str((res[b] - res[a - 1]) % mod))


(t, k) = map(int, input().split())
a = [0] * 100001
a[0] = 1
w = 1000000007
for i in range(1, len(a)):
	a[i] = a[i - 1] % w
	if i >= k:
		a[i] += a[i - k] % w
for i in range(1, len(a)):
	a[i] += a[i - 1]
	a[i] = a[i] % w
for i in range(t):
	(c, b) = map(int, input().split())
	print((a[b] - a[c - 1]) % w)


(t, k) = map(int, input().split())
dp = [0] * 100001
for i in range(k):
	dp[i] = 1
for i in range(k, 100001):
	dp[i] = dp[i - 1] + dp[i - k]
	dp[i] = dp[i] % 1000000007
su = [0] * 100001
su[0] = 1
for i in range(1, 100001):
	su[i] = su[i - 1] + dp[i]
	su[i] = su[i] % 1000000007
for i in range(t):
	(a, b) = map(int, input().split())
	ans = (su[b] - su[a - 1]) % 1000000007
	if ans < 0:
		print(0)
	else:
		print(ans)


(t, k) = input().split()
(t, k) = (int(t), int(k))
s = [0] * 100001
for i in range(k):
	s[i] = i + 1
for i in range(k, len(s)):
	s[i] = (s[i - 1] + s[i - k] + 1) % 1000000007
for i in range(t):
	(x, y) = input().split()
	print((s[int(y)] - s[int(x) - 1]) % 1000000007)


from sys import stdin, stdout
MOD = 10 ** 9 + 7
MAX = 10 ** 5 + 5
(t, k) = map(int, stdin.readline().split())
dp = [1] + [0] * MAX
for i in range(1, MAX + 1):
	dp[i] = (dp[i - 1] + (dp[i - k] if i - k >= 0 else 0)) % MOD
psums = [0]
for val in dp:
	psums.append((psums[-1] + val) % MOD)
sumRange = lambda left, right: (psums[right + 1] - psums[left]) % MOD
for _ in range(t):
	(a, b) = map(int, stdin.readline().split())
	stdout.write('%d\n' % sumRange(a, b))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7
(t, k) = [int(x) for x in input().split()]
dp = [-1 for x in range(100010)]

def solve(n):
	ans = 0
	if n == 0:
		return 1
	if dp[n] != -1:
		return dp[n]
	else:
		if n >= k:
			ans += solve(n - k)
			ans %= mod
		ans += solve(n - 1)
		ans %= mod
		dp[n] = ans
		return ans
psum = [0 for x in range(100010)]
for i in range(1, 100010):
	psum[i] = (psum[i - 1] + solve(i)) % mod
for i in range(t):
	(a, b) = [int(x) for x in input().split()]
	sys.stdout.write(str((psum[b] - psum[a - 1] + mod) % mod) + '\n')


MOD = 1000000007
lim = 100001
(t, k) = map(int, input().split())
A = [0] * lim
A[:k] = [1] * k
for i in range(k, lim):
	A[i] = (A[i - 1] + A[i - k]) % MOD
for i in range(1, lim):
	A[i] = (A[i - 1] + A[i]) % MOD
for i in range(t):
	(a, b) = map(int, input().split())
	print((A[b] - A[a - 1]) % MOD)


def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
M = 10 ** 9 + 7

def solve():
	(A, B) = getInts()
	return (dp_sum[B] - dp_sum[A - 1]) % M
(T, K) = getInts()
dp = [1 for i in range(K)]
dp_sum = dict()
sum_dp = K
for i in range(K):
	dp_sum[i] = i + 1
for i in range(K, 10 ** 5 + 1):
	(AA, BB) = (dp[i - K], dp[i - 1])
	dp.append((AA + BB) % M)
	sum_dp += AA + BB
	sum_dp %= M
	dp_sum[i] = sum_dp
for t in range(T):
	ans = solve()
	print(ans)


m = 10 ** 9 + 7
(t, k) = map(int, input().split())
dp = [0 for i in range(10 ** 5 + 1)]
dp[0] = 1
s = [0 for i in range(10 ** 5 + 1)]
s[0] = 1
for i in range(1, 10 ** 5 + 1):
	if i < k:
		dp[i] = 1
	else:
		dp[i] = (dp[i - 1] + dp[i - k]) % m
	s[i] = (s[i - 1] + dp[i]) % m
for i in range(t):
	(l, r) = map(int, input().split())
	print((s[r] + m - s[l - 1]) % m)


I = lambda : map(int, input().split())
(t, k) = I()
w = [1] + [0 for i in range(100001)]
for i in range(1, 100002):
	w[i] = (w[i - 1] + (w[i - k] if i > k else 0)) % 1000000007
l = [0]
for i in w:
	l.append((l[-1] + i) % 1000000007)
tc = [I() for i in range(t)]
for (a, b) in tc:
	print((l[b + 2] - l[a + 1]) % 1000000007)


from itertools import accumulate
mod = 10 ** 9 + 7
(t, k) = list(map(int, input().split()))
arr = [0] * 100001
for i in range(1, k):
	arr[i] = 1
arr[k] = 2
for i in range(k + 1, 100001):
	arr[i] = (arr[i - 1] + arr[i - k]) % mod
arr = list(accumulate(arr))
for i in range(t):
	(a, b) = list(map(int, input().split()))
	result = (arr[b] - arr[a - 1] + mod) % mod
	print(result)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
sys.setrecursionlimit(int(pow(10, 6)))
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
(t, k) = l()
dp = [1 for i in range(10 ** 5 + 1)]
dp[0] = 0
dp[k] = 2
for i in range(k + 1, 10 ** 5 + 1):
	dp[i] = (dp[i - 1] + dp[i - k]) % mod
pref = [0 for i in range(10 ** 5 + 2)]
for i in range(1, 10 ** 5 + 2):
	pref[i] = (pref[i - 1] + dp[i - 1]) % mod
for _ in range(t):
	(a, b) = l()
	print((pref[b + 1] - pref[a]) % mod)


(t, k) = [int(i) for i in input().split()]
dp = [0 for i in range(10 ** 5 + 5)]
dp[0] = 1
MOD = 10 ** 9 + 7
for i in range(1, 10 ** 5 + 5):
	if i < k:
		dp[i] = dp[i - 1]
	else:
		dp[i] = (dp[i - 1] + dp[i - k]) % MOD
pref = [0 for i in range(10 ** 5 + 5)]
pref[0] = 1
for i in range(1, 10 ** 5 + 5):
	pref[i] = (pref[i - 1] + dp[i]) % MOD
pref.append(0)
for q in range(t):
	(a, b) = [int(i) for i in input().split()]
	print((pref[b] - pref[a - 1]) % MOD)


MOD = 10 ** 9 + 7
(t, k) = [int(x) for x in input().split()]
dp = [0 for i in range(100005)]
dp[0] = 1
for i in range(1, len(dp)):
	dp[i] = dp[i - 1]
	if i < k:
		continue
	dp[i] += dp[i - k]
	dp[i] %= MOD
pref = [0 for i in range(len(dp) + 1)]
pref[0] = dp[0]
for i in range(1, len(dp)):
	pref[i] += pref[i - 1] + dp[i]
	pref[i] %= MOD
for i in range(t):
	(a, b) = [int(x) for x in input().split()]
	ans = (pref[b] - pref[a - 1] + MOD) % MOD
	print(ans)


(a, b) = map(int, input().split())
t = b
z = [i for i in range(1, b + 1)]
while t < 100001:
	z += [(z[t - 1] + z[t - b] + 1) % 1000000007]
	t += 1
for i in range(a):
	(x, y) = map(int, input().split())
	print((z[y] - z[x - 1]) % 1000000007)


def main():
	mode = 'filee'
	if mode == 'file':
		f = open('test.txt', 'r')
	get = lambda : [int(x) for x in (f.readline() if mode == 'file' else input()).split()]
	mod = 1000000007
	[t, k] = get()
	x = [1] * 100001
	for i in range(k, 100001):
		x[i] = (x[i - 1] + x[i - k]) % mod
	for i in range(1, 100001):
		x[i] = (x[i] + x[i - 1]) % mod
	for i in range(t):
		[a, b] = get()
		print((x[b] - x[a - 1]) % mod)
	if mode == 'file':
		f.close()
main()


(t, k) = map(int, input().split())
m = 1000000007
r = list(range(1, k + 1))
for i in range(k, 100001):
	r.append((r[i - 1] + r[i - k] + 1) % m)
for i in range(t):
	(a, b) = map(int, input().split())
	print((r[b] - r[a - 1]) % m)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
(t, k) = mp()
l = []
c = 0
for _ in range(t):
	(a, b) = mp()
	l.append([a, b])
	c = max(c, b)
dp = [1 for i in range(c + 1)]
pre = list(dp)
for i in range(1, k):
	pre[i] = pre[i - 1] + 1
	pre[i] %= mod
for i in range(k, c + 1):
	dp[i] = dp[i - k] + dp[i - 1]
	dp[i] %= mod
	pre[i] = pre[i - 1] + dp[i]
	pre[i] %= mod
for i in l:
	(a, b) = i
	ans = (pre[b] - pre[a - 1] + mod) % mod
	pr(ans)


from itertools import accumulate
mod = 1000000007
(t, k) = map(int, input().split())
req = []
mx = float('-inf')
for _ in range(t):
	(a, b) = map(int, input().split())
	req.append((a, b))
	mx = max(b, mx)
arr = [0 for _ in range(mx + 1)]
arr[0] = 1
for i in range(1, mx + 1):
	arr[i] = (arr[i - 1] + (arr[i - k] if i - k >= 0 else 0)) % mod
arr = list(accumulate(arr))
for (a, b) in req:
	print((arr[b] - arr[a - 1]) % mod)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log, pi, sin
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
(t, k) = sp()
dp = dd(int)
if k == 1:
	dp[1] = 2
	for i in range(2, 100001):
		dp[i] = dp[i - 1] * 2
		dp[i] %= mod
else:
	for i in range(1, k):
		dp[i] = 1
	dp[k] = 2
	for i in range(k + 1, 100001):
		dp[i] = dp[i - 1] + dp[i - k]
		dp[i] %= mod
for i in range(1, 100001):
	dp[i] += dp[i - 1]
for _ in range(t):
	(a, b) = sp()
	out((dp[b] - dp[a - 1] + mod) % mod)


M = 10 ** 9 + 7
(t, k) = map(int, input().split())
L = [tuple(map(int, input().split())) for i in range(t)]
ways = [0] * (1 + max(map(max, L)))
ways[0] = 1
for i in range(1, len(ways)):
	ways[i] = ways[i - 1] % M
	if i >= k:
		ways[i] = (ways[i] + ways[i - k]) % M
for i in range(1, len(ways)):
	ways[i] += ways[i - 1]
for (i, (a, b)) in enumerate(L):
	print((ways[b] - ways[a - 1]) % M)


(t, k) = map(int, input().split())
(lst, mx) = ([], 0)
from sys import stdin
for i in range(t):
	(a, b) = map(int, stdin.readline().split())
	lst.append([a, b])
	if mx < b:
		mx = b
(res1, res2, result) = ([0], [0], 2)
(ap1, ap2) = (res1.append, res2.append)
for i in range(1, k):
	ap1(i)
	ap2(1)
for i in range(k, mx + 1):
	ap2(result)
	ap1(result + res1[i - 1] % 1000000007)
	result = result + res2[i - k + 1] % 1000000007
for (i, x) in enumerate(lst):
	(a, b) = (x[0], x[1])
	print((res1[b] - res1[a - 1]) % 1000000007)


(n, k) = [int(j) for j in input().split()]
a = [1 for _ in range(100001)]
for i in range(k, 100001):
	a[i] = (a[i - 1] + a[i - k]) % 1000000007
for i in range(1, 100001):
	a[i] = (a[i - 1] + a[i]) % 1000000007
for _ in range(n):
	(r, b) = [int(j) for j in input().split()]
	print((a[b] - a[r - 1]) % 1000000007)


(t, k) = map(int, input().split())
MOD = int(1000000000.0) + 7

def madd(a, b):
	if a + b >= MOD:
		return a + b - MOD
	return a + b

def msub(a, b):
	if a >= b:
		return a - b
	return a - b + MOD
dp = [0] * 100001
dp[0] = 1
prefix = [0] * 100001
for i in range(1, 100001):
	dp[i] = dp[i - 1]
	if i >= k:
		dp[i] = madd(dp[i], dp[i - k])
	prefix[i] = madd(prefix[i - 1], dp[i])
for _ in range(t):
	(a, b) = map(int, input().split())
	print(msub(prefix[b], prefix[a - 1]))


mod = 1000000007
(n, k) = map(int, input().split())
dp = [i for i in range(1, k + 1)]
for i in range(k, 100001):
	dp.append((dp[i - 1] + dp[i - k] + 1) % mod)
for i in range(n):
	(a, b) = map(int, input().split())
	print((dp[b] - dp[a - 1]) % mod)


(n, k) = map(int, input().split())
j = 100001
modder = 1000000007
a = [1] * j
for i in range(k, j):
	a[i] = (a[i - 1] + a[i - k]) % modder
for i in range(1, j):
	a[i] = (a[i] + a[i - 1]) % modder
for _ in range(n):
	(l, r) = map(int, input().split())
	print((a[r] - a[l - 1]) % modder)


import sys
(t, k) = list(map(int, sys.stdin.readline().strip().split()))
modu = 10 ** 9 + 7
n = 10 ** 5 + 1
arr = [0] * n
arr[0] = 1
for i in range(1, n):
	arr[i] = (arr[i - 1] + (0 if i < k else arr[i - k])) % modu
for i in range(1, n):
	arr[i] = (arr[i] + arr[i - 1]) % modu
for i in range(t):
	(a, b) = list(map(int, sys.stdin.readline().strip().split()))
	print((arr[b] - arr[a - 1] + modu) % modu)


from sys import stdin, stdout
input = stdin.readline

def main():
	(t, k) = map(int, input().split())
	mod = 10 ** 9 + 7
	num = 10 ** 5
	n = num + k + 2
	dp = [0] * n
	dp[0] = 1
	for i in range(num):
		dp[i + 1] += dp[i]
		dp[i + 1] %= mod
		dp[i + k] += dp[i]
		dp[i + k] %= mod
	su = [0] * n
	for i in range(n):
		su[i] = su[i - 1] + dp[i]
		su[i] %= mod
	for i in range(t):
		(a, b) = map(int, input().split())
		print((su[b] - su[a - 1]) % mod)
main()


dp = [0] * (10 ** 5 + 1)
dp[0] = 1
mod = 10 ** 9 + 7
(t, k) = map(int, input().split())
for i in range(1, 10 ** 5 + 1):
	dp[i] = (dp[i - 1] + (dp[i - k] if i >= k else 0)) % mod
for i in range(1, 10 ** 5 + 1):
	dp[i] = (dp[i] + dp[i - 1]) % mod
for i in range(t):
	(a, b) = map(int, input().split())
	print((dp[b] - dp[a - 1]) % mod)


from sys import *
inp = lambda : stdin.readline()
mod = 1000000007
N = int(100000.0 + 5)

def main():
	(t, k) = map(int, inp().split())
	dp = [1 for i in range(N)]
	sum = dp[:]
	for i in range(N):
		if i >= k:
			dp[i] = (dp[i - k] + dp[i - 1]) % mod
	sum[0] = dp[0]
	for i in range(1, N):
		sum[i] = (sum[i - 1] + dp[i]) % mod
	for i in range(t):
		(a, b) = map(int, inp().split())
		print((sum[b] - sum[a - 1]) % mod)
main()


mod = 1000000007
(t, k) = list(map(int, input().split()))
dp = [0 for _ in range(100000 + 1)]
dp[0] = 1
if k == 1:
	dp[1] = 2
else:
	dp[1] = 1
for i in range(2, len(dp)):
	if i >= k:
		dp[i] = (dp[i - k] + dp[i - 1]) % mod
	else:
		dp[i] = dp[i - 1] % mod
prefix_dp = [0 for _ in range(len(dp))]
for i in range(1, len(dp)):
	prefix_dp[i] = (prefix_dp[i - 1] + dp[i]) % mod
for i in range(t):
	(a, b) = list(map(int, input().split()))
	print((prefix_dp[b] - prefix_dp[a - 1]) % mod)


from sys import stdin, stdout
dp = [1] * 100001
(n, k) = map(int, stdin.readline().split())
(n, k) = [int(n), int(k)]
for i in range(k, 100001):
	dp[i] = (dp[i - 1] + dp[i - k]) % 1000000007
for i in range(1, 100001):
	dp[i] = (dp[i] + dp[i - 1]) % 1000000007
for i in range(0, n):
	(a, b) = map(int, stdin.readline().split())
	(a, b) = [int(a), int(b)]
	ans = (dp[b] - dp[a - 1]) % 1000000007
	stdout.write(str(ans) + '\n')


mod = 10 ** 9 + 7
(t, k) = map(int, input().strip().split())
ranges = []
maxi = 10 ** 5
dp = [0 for i in range(maxi + 1)]
dp[0] = 1
for i in range(1, maxi + 1):
	if i >= k:
		dp[i] = (dp[i - 1] + dp[i - k]) % mod
	else:
		dp[i] = dp[i - 1]
for i in range(1, maxi + 1):
	dp[i] = (dp[i] + dp[i - 1]) % mod
for i in range(t):
	ranges.append(list(map(int, input().strip().split())))
for i in ranges:
	print((dp[i[1]] - dp[i[0] - 1]) % mod)


(t, k) = list(map(int, input().strip().split()))
modu = 10 ** 9 + 7
n = 10 ** 5 + 1
arr = [0] * n
for i in range(k):
	arr[i] = 1
for i in range(k, n):
	arr[i] = (arr[i - 1] + arr[i - k]) % modu
for i in range(1, n):
	arr[i] = (arr[i] + arr[i - 1]) % modu
for i in range(t):
	(a, b) = list(map(int, input().strip().split()))
	print((arr[b] - arr[a - 1] + modu) % modu)


import bisect
from itertools import accumulate
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def SieveOfEratosthenes(n):
	prime = []
	primes = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if primes[p] == True:
			prime.append(p)
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	return prime

def primefactors(n):
	fac = []
	while n % 2 == 0:
		fac.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 2):
		while n % i == 0:
			fac.append(i)
			n = n // i
	if n > 1:
		fac.append(n)
	return sorted(fac)

def factors(n):
	fac = set()
	fac.add(1)
	fac.add(n)
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			fac.add(i)
			fac.add(n // i)
	return list(fac)

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
(t, k) = map(int, input().split())
dp = [0] * (10 ** 5 + 1)
for i in range(0, k):
	dp[i] = 1
for i in range(k, 10 ** 5 + 1):
	dp[i] = (dp[i - 1] + dp[i - k]) % (10 ** 9 + 7)
ans = [0] + list(accumulate(dp[1:]))
for i in range(t):
	(a, b) = map(int, input().split())
	print((ans[b] - ans[a - 1]) % (10 ** 9 + 7))


(t, k) = map(int, input().split())
dp = []
for i in range(k - 1):
	dp.append(1)
mod = 10 ** 9 + 7
dp.append(2)
for i in range(k, 10 ** 5):
	dp.append((dp[i - 1] + dp[i - k]) % mod)
for i in range(1, 10 ** 5):
	dp[i] = (dp[i] + dp[i - 1]) % mod
for _ in range(t):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	ans = dp[b]
	if a != 0:
		ans = (ans - dp[a - 1] + mod) % mod
	print(ans)


mod = 1000000007
(t, k) = map(int, input().split())
dp = [1] * k
for i in range(k, 100005):
	dp.append((dp[i - 1] + dp[i - k]) % mod)
for i in range(1, 100005):
	dp[i] = (dp[i] + dp[i - 1]) % mod
for _ in range(t):
	(a, b) = map(int, input().split())
	ans = dp[b] - dp[a - 1]
	if ans < 0:
		ans += mod
	print(ans)


(n, k) = map(int, input().split())
a = [1]
m = 100000
d = 1000000007
for i in range(1, m + 1):
	if i < k:
		a.append(1)
	else:
		a.append((a[i - 1] % d + a[i - k] % d) % d)
for i in range(1, m + 1):
	if i == 1:
		pass
	else:
		a[i] = (a[i] % d + a[i - 1] % d) % d
a[0] = 0
for i in range(n):
	(x, y) = map(int, input().split())
	print((a[y] - a[x - 1]) % d)


m = 1000000007
(t, k) = [int(i) for i in input().split(' ')]
n = 100000
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
	dp[i] = (dp[i - 1] + (0 if i - k < 0 else dp[i - k])) % m
s = [0] * (n + 1)
s[1] = dp[1]
s[0] = 0
for i in range(2, n + 1):
	s[i] = (s[i - 1] + dp[i]) % m
for _ in range(t):
	(a, b) = [int(i) for i in input().split(' ')]
	print((s[b] - s[a - 1] + m) % m)


(t, k) = [int(x) for x in input().split(' ')]
d = [1]
c = [1]
l = 1
for i in range(1, 10 ** 5 + 1):
	v = d[i - 1] + (d[i - k] if i - k >= 0 else 0)
	v %= 10 ** 9 + 7
	d.append(v)
	c.append((v + l) % (10 ** 9 + 7))
	l = (v + l) % (10 ** 9 + 7)
for _ in range(t):
	(a, b) = [int(x) for x in input().split(' ')]
	s = c[b] - c[a - 1]
	print(str(s) if s >= 0 else str(10 ** 9 + 7 + s))


(t, k) = map(int, input().split())
MAXV = int(100000.0) + 10
MOD = int(1000000000.0) + 7
dp = [1]
for i in range(1, MAXV):
	tmp = dp[i - 1]
	if i - k >= 0:
		tmp += dp[i - k] % MOD
	dp.append(tmp)
for i in range(1, MAXV):
	dp[i] += dp[i - 1]
	dp[i] %= MOD
for i in range(t):
	(a, b) = map(int, input().split())
	ans = (dp[b] - dp[a - 1]) % MOD
	print(ans)


(m, b) = (1000000007, 100001)
c = lambda : map(int, input().split())
a = [1] * b
(t, k) = c()
for i in range(k, b):
	a[i] = (a[i - 1] + a[i - k]) % m
for i in range(1, b):
	a[i] = (a[i] + a[i - 1]) % m
while t:
	t -= 1
	(x, y) = c()
	print((a[y] - a[x - 1]) % m)


def solve(n):
	if n == 0:
		return 1
	if dp[n] != -1:
		return dp[n]
	(w, r) = (0, 0)
	if n >= k:
		w = solve(n - k)
	r = solve(n - 1)
	dp[n] = (w + r) % mod
	return dp[n]

def make_prefix():
	for i in range(1, max_l + 1):
		prefix[i] = prefix[i - 1] + solve(i)
		prefix[i] = prefix[i] % mod
mod = 1000000007
max_l = 10 ** 5
dp = [-1 for i in range(max_l + 1)]
prefix = [-1 for i in range(max_l + 1)]
(t, k) = map(int, input().strip().split())
make_prefix()
for m in range(t):
	(a, b) = map(int, input().strip().split())
	print((prefix[b] - prefix[a - 1] + mod) % mod)


from sys import stdin, stdout, stderr
(t, k) = map(int, input().split())
mod = int(1000000007)

def fast(a, b):
	res = 1
	while b:
		if b & 1:
			res = res * a % mod
		a = a * a % mod
		b = b // 2
	return res
dp = [1 for i in range(k)]
for i in range(k, 100005, 1):
	dp.append((dp[i - 1] + dp[i - k]) % mod)
for i in range(1, 100005, 1):
	dp[i] = (dp[i - 1] + dp[i]) % mod
for _ in range(t):
	(a, b) = map(int, input().split())
	print((dp[b] - dp[a - 1] + mod) % mod)


import sys
input = sys.stdin.readline
(t, k) = map(int, input().split())
s = [0] * (10 ** 5 + 2)
s[0] = 1
sm = [0] * (10 ** 5 + 2)
sm[0] = 1
for i in range(1, 10 ** 5 + 2):
	ind1 = i - 1
	ind2 = i - k
	if ind2 < 0:
		s[i] = s[ind1] % 1000000007
	else:
		s[i] = (s[ind1] + s[ind2]) % 1000000007
	sm[i] = sm[i - 1] + s[i]
for _ in range(t):
	(a, b) = map(int, input().split())
	print((sm[b] - sm[a - 1]) % 1000000007)


import sys
input = sys.stdin.readline
pri = 10 ** 9 + 7
(ar, y) = map(int, input().split())
x = [0 for i in range(10 ** 5 + 1)]
for i in range(len(x)):
	if i < y:
		x[i] = 1
	else:
		x[i] = (x[i - 1] % pri + x[i - y] % pri) % pri
sume = [0]
for i in range(1, len(x)):
	sume.append((sume[-1] + x[i]) % pri)
for i in range(ar):
	(a, b) = map(int, input().split())
	print((sume[b] - sume[a - 1]) % pri)


(t, k) = map(int, input().split())
dp = [0] * (10 ** 5 + 1)
mod = 10 ** 9 + 7
i = 1
while i < k:
	dp[i] = 1
	i += 1
dp[k] = 2
for i in range(k + 1, 10 ** 5 + 1):
	dp[i] = (dp[i - 1] + dp[i - k]) % mod
for i in range(1, 10 ** 5 + 1):
	dp[i] += dp[i - 1]
for i in range(t):
	(a, b) = map(int, input().split())
	print((dp[b] - dp[a - 1]) % mod)


import sys
import math
import bisect
import heapq
from bisect import bisect_right
from sys import stdin, stdout

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(sys.stdin.readline())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def Solution():
	(t, k) = get_ints_in_variables()
	mod = pow(10, 9) + 7
	dp = [0 for _ in range(pow(10, 5) + 5)]
	dp[0] = 1
	for i in range(1, pow(10, 5) + 1):
		if i < k:
			dp[i] = dp[i - 1] % mod
		else:
			dp[i] = (dp[i - 1] % mod + dp[i - k] % mod) % mod
	prefix = [0]
	for v in dp:
		prefix.append((prefix[-1] % mod + v % mod) % mod)
	prefix.pop(0)
	for _ in range(t):
		(a, b) = get_ints_in_variables()
		print((prefix[b] - prefix[a] + dp[a]) % mod)

def main():
	Solution()
main()


(t, k) = map(int, input().split())
(n, m) = (100001, 1000000007)
(p, r) = ([0] * n, [0] * n)
p[:k] = [1] * k
for i in range(k, n):
	p[i] = (p[i - 1] + p[i - k]) % m
for i in range(1, n):
	p[i] = (p[i] + p[i - 1]) % m
for i in range(t):
	(a, b) = map(int, input().split())
	print((p[b] - p[a - 1]) % m)


from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)
import sys

def I():
	return int(stdin.readline())

def lint():
	return [int(x) for x in stdin.readline().split()]

def S():
	return input().strip()

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter
import math
import heapq
from heapq import heappop, heappush
import bisect
from itertools import groupby

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

def lcm(a, b):
	return a // gcd(a, b) * b

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def Bs(a, x):
	i = 0
	j = 0
	left = 1
	right = x
	flag = False
	while left < right:
		mi = (left + right) // 2
		if a[mi] <= x:
			left = mi + 1
			i += 1
		else:
			right = mi
			j += 1
	if left > 0 and a[left - 1] == x:
		return (i - 1, j)
	else:
		return (-1, -1)

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num

def ask(a):
	print('? {}'.format(a), flush=True)
	n = I()
	return n

def dfs(i, p):
	(a, tmp) = (0, 0)
	for j in d[i]:
		if j != p:
			a += 1
			tmp += dfs(j, i)
	if a == 0:
		return 0
	return tmp / a + 1

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	if n > 2:
		l.append(n)
	return l
(t, k) = lint()
dp = [1] * (10 ** 5 + 1)
for i in range(k, 10 ** 5 + 1):
	dp[i] = (dp[i - 1] + dp[i - k]) % mod
for i in range(1, 10 ** 5 + 1):
	dp[i] = (dp[i] + dp[i - 1]) % mod
for i in range(t):
	(l, r) = lint()
	print((dp[r] - dp[l - 1]) % mod)


(t, k) = map(int, input().split())
l = []
ma = 0
m = 10 ** 9 + 7
for _ in range(t):
	(a, b) = map(int, input().split())
	l.append((a, b))
	ma = max(ma, a, b)
dp = [0] * (ma + 1)
for i in range(ma + 1):
	if i < k:
		dp[i] = 1
	else:
		dp[i] = (dp[i - 1] % m + dp[i - k] % m) % m
su = [0]
for i in range(1, ma + 1):
	su.append((su[-1] % m + dp[i] % m) % m)
for i in range(t):
	print((su[l[i][1]] % m - su[l[i][0] - 1] % m) % m)


(t, k) = map(int, input().split())
d = [0] * 10 ** 5
mod = 10 ** 9 + 7
for lenght in range(k - 1):
	d[lenght] = 1
d[k - 1] = 2
for i in range(k, 10 ** 5):
	d[i] = (d[i - 1] + d[i - k]) % mod
f = [0]
for i in range(10 ** 5):
	f.append((f[i] + d[i]) % mod)
for _ in range(t):
	(a, b) = map(int, input().split())
	print((f[b] - f[a - 1]) % mod)


(t, k) = map(int, input().split())
length = [0] * (10 ** 5 + 1)
length[0] = 1
mod = 10 ** 9 + 7
for i in range(1, 10 ** 5 + 1):
	if i >= k:
		length[i] += length[i - k]
	length[i] = (length[i] + length[i - 1]) % mod
pref = [0]
for i in range(1, len(length)):
	pref.append(pref[-1] + length[i])
for i in range(t):
	(a, b) = map(int, input().split())
	print((pref[b] - pref[a - 1]) % mod)


from sys import stdin, stdout
modconst = 1000000007
(n, k) = map(int, stdin.readline().split())
f = [0] * 100001
ss = [0] * 100001
f[0] = 0
for i in range(1, k):
	f[i] = 1
f[k] = 2
for i in range(k + 1, 100001):
	f[i] = (f[i - 1] + f[i - k]) % modconst
ss[0] = 0
for i in range(1, 100001):
	ss[i] = (ss[i - 1] + f[i]) % modconst
for i in range(n):
	(a, b) = map(int, stdin.readline().split())
	stdout.write(str((ss[b] - ss[a - 1] + modconst) % modconst) + '\n')


def hehe(b, k):
	count = [-1] * (b + 1)
	count[0] = 1
	sum = [-1] * (b + 1)
	sum[0] = 1
	for i in range(1, b + 1, 1):
		count[i] = count[i - 1] % 1000000007
		if i >= k:
			count[i] += count[i - k] % 1000000007
		count[i] %= 1000000007
		sum[i] = count[i] % 1000000007 + sum[i - 1] % 1000000007
		sum[i] %= 1000000007
	return sum
(n, k) = input().split()
n = int(n)
k = int(k)
a = [0] * n
b = -1
for i in range(0, n, 1):
	a[i] = input().split()
	a[i] = [int(j) for j in a[i]]
	if a[i][1] > b:
		b = a[i][1]
sum = hehe(b, k)
for i in range(0, n, 1):
	print((sum[a[i][1]] - sum[a[i][0] - 1]) % 1000000007)


import sys
(t, k) = input().split()
t = int(t)
k = int(k)
c = 10 ** 9 + 7
n = 10 ** 5 + 1
DP = []
DP.append(1)
for i in range(1, n):
	if i - k < 0:
		DP.append(DP[i - 1] % c)
	else:
		DP.append((DP[i - 1] + DP[i - k]) % c)
SUM = [0]
for i in range(1, n):
	SUM.append((SUM[i - 1] + DP[i]) % c)
for i in range(0, t):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	sys.stdout.write(str((SUM[b] - SUM[a - 1]) % c) + '\n')


sum_ = []
L = int(100000.0) + 1
md = int(1000000000.0) + 7

def calculate(k, L):
	sum_.append(0)
	for i in range(1, k):
		sum_.append(i)
	for i in range(k, L):
		sum_.append((sum_[i - 1] + sum_[i - k] + 2) % md)
(t, k) = map(int, input().split())
calculate(k, L)
for _ in range(t):
	(a, b) = map(int, input().split())
	print((sum_[b] - sum_[a - 1]) % md)


def getans(n):
	if n == 0:
		return 1
	if dp[n] != -1:
		return dp[n]
	ans = 0
	if n >= k:
		ans += getans(n - k)
		ans = ans % mod
	ans += getans(n - 1)
	ans = ans % mod
	dp[n] = ans % mod
	return dp[n]

def init():
	for i in range(1, 10 ** 5 + 1):
		pre.append((pre[-1] + getans(i)) % mod)
(t, k) = map(int, input().split())
dp = [-1] * (10 ** 5 + 1)
pre = [0]
mod = int(1000000000.0) + 7
init()
for _ in range(t):
	(a, b) = map(int, input().split())
	print((pre[b] - pre[a - 1] + mod) % mod)


mod = 10 ** 9 + 7
(t, k) = map(int, input().split())
pp = [i for i in range(1, k + 1)]
for j in range(k, 10 ** 6 + 1):
	pp.append((pp[j - 1] + pp[j - k] + 1) % mod)
for _ in range(t):
	(a, b) = map(int, input().split())
	print((pp[b] - pp[a - 1]) % mod)


(t, k) = map(int, input().split())
mod = 1000000007
ans = [1] * 100001
for x in range(k, 100001):
	ans[x] = (ans[x - 1] + ans[x - k]) % mod
for x in range(1, 100001):
	ans[x] = (ans[x] + ans[x - 1]) % mod
for x in range(t):
	(a, b) = map(int, input().split())
	print((ans[b] - ans[a - 1]) % mod)


(t, k) = map(int, input().split(' '))
values = [0] + [1] + [0] * (10 ** 5 + 10)
sums = [0] + [1] + [0] * (10 ** 5 + 10)
for i in range(2, 10 ** 5 + 10):
	values[i] = (values[i - 1] + values[max(0, i - k)]) % (10 ** 9 + 7)
	sums[i] = (sums[i - 1] + values[i]) % (10 ** 9 + 7)
for i in range(t):
	(a, b) = map(int, input().split(' '))
	print((sums[b + 1] - sums[a]) % (10 ** 9 + 7))


class Solution:

	def __init__(self):
		self.ln = 10 ** 5 + 1
		self.dp = [0] * self.ln

	def initiate(self, k):
		self.dp[0] = 1
		P = 10 ** 9 + 7
		for i in range(1, self.ln):
			self.dp[i] = self.dp[i - 1]
			if i >= k:
				self.dp[i] = (self.dp[i] + self.dp[i - k]) % P
		for i in range(1, self.ln):
			self.dp[i] = (self.dp[i] + self.dp[i - 1]) % P

	def calculate(self, a, b):
		P = 10 ** 9 + 7
		return ((self.dp[b] - self.dp[a - 1]) % P + P) % P
(t, k) = list(map(int, input().strip().split(' ')))
sol = Solution()
sol.initiate(k)
for i in range(t):
	(a, b) = list(map(int, input().strip().split(' ')))
	print(sol.calculate(a, b))


def main():
	MAX = 1000000007
	(T, K) = [int(i) for i in input().split()]
	fib = [1 for i in range(K)]
	for i in range(K, 100001):
		fib.append((fib[i - 1] + fib[i - K]) % MAX)
	s = [0]
	for i in range(1, 100001):
		s.append((s[i - 1] + fib[i]) % MAX)
	for t in range(T):
		(a, b) = [int(i) for i in input().split()]
		print((s[b] - s[a - 1]) % MAX)
main()


(t, k) = list(map(int, input().split()))
dp = [1] * k
i = k
while i <= 10 ** 5:
	dp.append((dp[i - 1] + dp[i - k]) % (10 ** 9 + 7))
	i += 1
for i in range(1, 10 ** 5 + 1):
	dp[i] += dp[i - 1]
for itr in range(t):
	(a, b) = list(map(int, input().split()))
	print((dp[b] - dp[a - 1]) % (10 ** 9 + 7))


(t, k) = map(int, input().split())
sums = [0, 1]
a = [0, 1]
output = []
mod = 10 ** 9 + 7
for i in range(2, 100005):
	if i - k > 0:
		a.append(a[i - k])
	else:
		a.append(0)
	a[i] += a[i - 1]
	a[i] %= mod
	sums.append((sums[i - 1] + a[i]) % mod)
for i in range(t):
	(a, b) = map(int, input().split())
	output.append(str((mod + sums[b + 1] - sums[a]) % mod))
print('\n'.join(output))


from sys import stdin, stdout
(t, k) = stdin.readline().split()
t = int(t)
k = int(k)
dp = [1]
mod = 1000000007
for i in range(1, 100001):
	dp.append(dp[i - 1])
	if i - k >= 0:
		dp[i] += dp[i - k]
	dp[i] %= mod
for i in range(1, 100001):
	dp[i] = dp[i] + dp[i - 1]
	dp[i] %= mod
for i in range(1, t + 1):
	(n, k) = stdin.readline().split()
	a = int(n)
	b = int(k)
	c = min(a, b)
	b = max(a, b)
	a = c
	print((dp[b] % mod - dp[a - 1] % mod) % mod)


arr = [0] * 100001
BIG = int(1000000000.0 + 7)
(t, k) = map(int, input().split())
for i in range(1, k + 1):
	arr[i] = 1
arr[k] = 2
for i in range(k + 1, 100001):
	arr[i] = (arr[i - 1] + arr[i - k]) % BIG
for i in range(1, 100001):
	arr[i] = (arr[i] + arr[i - 1]) % BIG
for _ in range(t):
	(a, b) = map(int, input().split())
	print((arr[b] - arr[a - 1] + BIG) % BIG)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass
(t, k) = L()
A = [L() for i in range(t)]
x = max((A[i][1] for i in range(t)))
dp = [1 for i in range(10 ** 5 + 2)]
z = sum(dp[:k]) % mod
for i in range(k, x + 1):
	z = (dp[i - k] + dp[i - 1]) % mod
	dp[i] = z
pref = [0 for i in range(x + 2)]
for i in range(1, x + 2):
	pref[i] = (pref[i - 1] + dp[i - 1]) % mod
for (i, j) in A:
	print((pref[j + 1] - pref[i]) % mod)
endtime = time.time()


(t, k) = map(int, input().split())
pre = [0] * (10 ** 5 + 1)
dp = [-1] * (10 ** 5 + 1)
MOD = 1000000007

def psum(n):
	ans = 0
	if n == 0:
		return 1
	if dp[n] != -1:
		return dp[n]
	if n >= k:
		ans = (ans + psum(n - k)) % MOD
	ans = (ans + psum(n - 1)) % MOD
	dp[n] = ans
	return dp[n]

def presum():
	for i in range(1, 10 ** 5 + 1):
		pre[i] = (pre[i - 1] + psum(i)) % MOD
presum()
while t:
	(a, b) = map(int, input().split())
	sum = (pre[b] - pre[a - 1]) % MOD
	print(sum)
	t -= 1


(n, k) = map(int, input().split())
r = []
for _ in range(n):
	(x, y) = map(int, input().split())
	r.append([x, y])
m = max(r, key=lambda x: x[1])[1]
dp = [1 for _ in range(m + 1)]
for i in range(1, m + 1):
	dp[i] = dp[i - 1] + (dp[i - k] if i - k >= 0 else 0)
	dp[i] %= 10 ** 9 + 7
s = [dp[i] for i in range(m + 1)]
for i in range(1, m + 1):
	s[i] += s[i - 1]
for x in r:
	print((s[x[1]] + 10 ** 9 + 7 - s[x[0] - 1]) % (10 ** 9 + 7))


mod = 10 ** 9 + 7

def calc(k):
	dp = [0] * 100005
	dp[0] = 1
	for i in range(1, len(dp)):
		if i < k:
			dp[i] = dp[i - 1]
		else:
			dp[i] = (dp[i - 1] % mod + dp[i - k] % mod) % mod
	for i in range(1, len(dp)):
		dp[i] = (dp[i - 1] % mod + dp[i] % mod) % mod
	return dp
(t, k) = map(int, input().split())
dp = calc(k)
for i in range(t):
	(a, b) = map(int, input().split())
	print((dp[b] - dp[a - 1] + mod) % mod)


(t, k) = map(int, input().split())
dp = [-1 for i in range(10 ** 5 + 1)]
dpm = [-1 for i in range(10 ** 5 + 1)]
mod = 10 ** 9 + 7

def getsol(n):
	if n == 0:
		return 1
	if dpm[n] != -1:
		return dpm[n]
	ans = 0
	if n >= k:
		ans = ans + getsol(n - k)
		ans = ans % mod
	ans = ans + getsol(n - 1)
	ans = ans % mod
	dpm[n] = ans % mod
	return dpm[n]

def init():
	dp[0] = 0
	for i in range(1, 10 ** 5 + 1):
		dp[i] = (dp[i - 1] + getsol(i)) % mod
init()
for _ in range(t):
	(a, b) = map(int, input().split())
	val = (dp[b] - dp[a - 1] + mod) % mod
	print(val)


(t, k) = map(int, input().split())
N = 100005
P = 1000 * 1000 * 1000 + 7
dp = [0 for _ in range(N)]
dp[0] = 1
for i in range(N):
	if i < k:
		dp[i] = 1
	else:
		dp[i] = (dp[i - k] + dp[i - 1]) % P
for i in range(1, N):
	dp[i] = (dp[i] + dp[i - 1]) % P
for _ in range(t):
	(a, b) = map(int, input().split())
	print((dp[b] - dp[a - 1] + P) % P)


vals = [0] * 100100
(t, k) = map(int, input().split())
vals[0] = 1
vals[1] = 1 + (k == 1)
for i in range(2, 100001):
	vals[i] = (vals[i - 1] + (vals[i - k] if i >= k else 0)) % 1000000007
for i in range(1, 100001):
	vals[i] = (vals[i - 1] + vals[i]) % 1000000007
for i in range(t):
	(a, b) = map(int, input().split())
	print((vals[b] - vals[a - 1]) % 1000000007)


mod = int(1000000000.0) + 7
(t, k) = map(int, input().split())
dp = [1] * 100001
for i in range(k, 100001):
	dp[i] = (dp[i - 1] + dp[i - k]) % mod
for i in range(1, 100001):
	dp[i] = (dp[i - 1] + dp[i]) % mod
for _ in range(t):
	(a, b) = map(int, input().split())
	print((dp[b] - dp[a - 1]) % mod)


MOD = 10 ** 9 + 7
(n, k) = map(int, input().split())
dp = [0 for _ in range(10 ** 5 + 2)]
for i in range(k):
	dp[i] = 1
for i in range(k, 10 ** 5 + 1):
	dp[i] = dp[i - 1] + dp[i - k]
	dp[i] %= MOD
for i in range(1, 10 ** 5 + 1):
	dp[i] += dp[i - 1]
	dp[i] %= MOD
for _ in range(n):
	(l, r) = map(int, input().split())
	ans = (dp[r] - dp[l - 1] + MOD) % MOD
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import threading
sys.setrecursionlimit(400000)
threading.stack_size(10 ** 8)

def flowers(n):
	global k, l, mod
	if n < k:
		return 1
	if l[n] != 0:
		return l[n]
	ans = 0
	ans = (flowers(n - k) + flowers(n - 1)) % mod
	l[n] = ans
	return ans

def main():
	global k, l, mod
	l = [0] * 100001
	l1 = [0] * 100001
	(t, k) = map(int, input().split())
	mod = 10 ** 9 + 7
	for i in range(k):
		l[i] = 1
	flowers(100000)
	l1[0] = l[0]
	for i in range(1, 100001):
		l1[i] = (l1[i - 1] + l[i]) % mod
	for i in range(t):
		(a, b) = map(int, input().split())
		print((l1[b] - l1[a - 1] + mod) % mod)
t = threading.Thread(target=main)
t.start()
t.join()


from sys import stdin, stdout
input = stdin.readline
mod = int(1000000000.0 + 7)
(t, k) = map(int, input().split())
p = []
for i in range(k - 1):
	p.append(1)
p.append(2)
for i in range(k, int(100000.0 + 2)):
	p.append((p[i - 1] % mod + p[i - k] % mod) % mod)
d = [0]
sn = 0
for i in p:
	sn = (sn % mod + i % mod) % mod
	d.append(sn)
for _ in range(t):
	(a, b) = map(int, input().split())
	sn = d[b] - d[a - 1]
	if sn < 0:
		sn += mod
	stdout.write(str(sn) + '\n')


from sys import stdin, stderr

def readInts():
	return map(int, stdin.readline().strip().split())

def print_err(*args, **kwargs):
	print(*args, file=stderr, **kwargs)

def solve(vs):
	return None

def naive(k, maxv):
	modval = 10 ** 9 + 7
	a = [1] * k
	tot = 0
	pfx_tots = []
	for x in a:
		tot += x
		pfx_tots.append(tot)
	for x in range(k, maxv):
		s = 2 * a[-k]
		if x - k - 1 >= 0:
			s += pfx_tots[x - k - 1]
		if x - 2 * k >= 0:
			s -= pfx_tots[x - 2 * k]
		s %= modval
		a.append(s)
		tot += s
		tot %= modval
		pfx_tots.append(tot)
	return (a, pfx_tots)

def run():
	modval = 10 ** 9 + 7
	(t, k) = readInts()
	(a, pfx) = naive(k, 10 ** 5 + 1)
	for _ in range(t):
		(lhs, rhs) = readInts()
		s = pfx[rhs]
		if lhs > 0:
			s -= pfx[lhs - 1]
		s %= modval
		print(s)
run()


L = input().split()
t = int(L[0])
k = int(L[1])
f = [1 for i in range(100002)]
qs = [0 for i in range(100002)]
qs[0] = 1
for i in range(1, 100001):
	if i < k:
		f[i] = 1
	else:
		f[i] = (f[i - 1] + f[i - k]) % 1000000007
	qs[i] = (qs[i - 1] + f[i]) % 1000000007
for i in range(t):
	L = input().split()
	a = int(L[0])
	b = int(L[1])
	print((qs[b] - qs[a - 1]) % 1000000007)


(t, k) = map(int, input().split())
MAXA = 10 ** 5 + 1
mod = 10 ** 9 + 7
f = [0] * MAXA
s = [0] * MAXA
for i in range(k):
	f[i] = 1
for i in range(k, MAXA):
	f[i] = (f[i - 1] + f[i - k]) % mod
for i in range(1, MAXA):
	s[i] = (s[i - 1] + f[i]) % mod
for i in range(t):
	(a, b) = map(int, input().split())
	result = (s[b] - s[a - 1] + mod) % mod
	print(result)


from itertools import accumulate

def adder(k):
	lst = [0 for i in range(10 ** 5 + 1)]
	for i in range(1, 10 ** 5 + 1):
		if i < k:
			lst[i] = 1
		elif i == k:
			lst[i] = 2
		else:
			lst[i] = (lst[i - 1] + lst[i - k]) % (10 ** 9 + 7)
	return lst
lst1 = list(map(lambda elem: int(elem), input().split(' ')))
[t, d] = lst1
if d == 0:
	[print(1) for i in range(t)]
else:
	sums = adder(d)
	prefix_sums = list(accumulate(sums))
	for i in range(t):
		lst2 = list(map(lambda elem: int(elem), input().split(' ')))
		[a, b] = lst2
		print((prefix_sums[b] - prefix_sums[a - 1]) % (10 ** 9 + 7))


MOD = 1000000007
MAX_N = 100002
dp = [None] * MAX_N
cumsum = [None] * (MAX_N + 1)
(t, k) = map(int, input().split())
for i in range(k):
	dp[i] = 1
for i in range(k, MAX_N):
	dp[i] = dp[i - 1] + dp[i - k]
	if dp[i] >= MOD:
		dp[i] -= MOD
cumsum[0] = 0
for i in range(MAX_N):
	cumsum[i + 1] = cumsum[i] + dp[i]
	if cumsum[i + 1] >= MOD:
		cumsum[i + 1] -= MOD
for _ in range(t):
	(a, b) = map(int, input().split())
	to_out = cumsum[b + 1] - cumsum[a]
	if to_out < 0:
		to_out += MOD
	print(to_out)


dp = [1] * 100001
(n, k) = input().split()
(n, k) = [int(n), int(k)]
for i in range(k, 100001):
	dp[i] = (dp[i - 1] + dp[i - k]) % 1000000007
for i in range(1, 100001):
	dp[i] = (dp[i] + dp[i - 1]) % 1000000007
for i in range(0, n):
	(a, b) = input().split()
	(a, b) = [int(a), int(b)]
	print((dp[b] - dp[a - 1]) % 1000000007)


MOD = 1000000007
(t, k) = map(int, input().split())
ls = [0] + [1] * 100000
ls[k] = 2
for i in range(k + 1, 100001):
	ls[i] = (ls[i - k] + ls[i - 1]) % MOD
for i in range(1, 100001):
	ls[i] = (ls[i] + ls[i - 1]) % MOD
for _ in range(t):
	(a, b) = map(int, input().split())
	print((ls[b] - ls[a - 1]) % MOD)


(t, k) = map(int, input().split())
dp = [1]
pre = [1]
arr = []
m = 0
for i in range(t):
	(a, b) = map(int, input().split())
	arr.append([a, b])
	m = max(m, b)
for i in range(m):
	dp.append(dp[-1])
	if i + 1 >= k:
		dp[-1] += dp[-k - 1]
		dp[-1] %= 10 ** 9 + 7
	pre.append(pre[-1] + dp[-1])
for i in range(t):
	(a, b) = arr[i]
	print((pre[b] - pre[a - 1]) % (10 ** 9 + 7))


import sys
input = lambda : list(map(int, sys.stdin.readline().split()))

def main():
	(t, k) = input()
	n = 10 ** 5 + 1
	f = [0] * n
	f[0] = 1
	mod = 10 ** 9 + 7
	for i in range(1, n):
		f[i] = f[i - 1] if i < k else f[i - k] + f[i - 1]
		f[i] %= mod
	for i in range(1, n):
		f[i] += f[i - 1]
	for _ in range(t):
		(a, b) = input()
		print((f[b] - f[a - 1]) % mod)
main()


(t, k) = map(int, input().split())
m = 1000000007
dp = [1] * (k - 1)
dp.append(2)
for i in range(k, 100000):
	dp.append((dp[i - 1] + dp[i - k]) % m)
s = [0]
for i in range(1, 100001):
	s.append((s[len(s) - 1] + dp[i - 1]) % m)
for query in range(t):
	(a, b) = map(int, input().split())
	ans = (s[b] - s[a - 1] + m) % m
	print(ans)


from sys import stdin, stdout
M = 10 ** 9 + 7
lim = 10 ** 5 + 5
dp = [0] * lim
(q, k) = list(map(int, stdin.readline().split()))
for i in range(lim):
	if i == 0:
		dp[i] = 1
	else:
		dp[i] = (dp[i - 1] + (dp[i - k] if i - k >= 0 else 0)) % M
for i in range(1, lim):
	dp[i] = (dp[i] + dp[i - 1]) % M
for _ in range(1):
	for _ in range(q):
		(a, b) = list(map(int, stdin.readline().split()))
		ans = (dp[b] - (dp[a - 1] if a >= 1 else 0) + M) % M
		print(ans)


mod = 1000000007
k = 2
pre = [0 for i in range(100001)]
dp = [0 for i in range(100001)]

def getans(n):
	if n == 0:
		return 1
	if dp[n] != -1:
		return dp[n]
	ans = 0
	if n >= k:
		ans += getans(n - k)
		ans = ans % 1000000007
	ans += getans(n - 1)
	ans = ans % 1000000007
	dp[n] = ans
	return dp[n]

def init():
	for i in range(1, 100001):
		dp[i] = -1
	for i in range(1, 100001):
		pre[i] = pre[i - 1] + getans(i)
		pre[i] = pre[i] % mod
tk = list(map(int, input().split()))
k = int(tk[1])
init()
for i in range(int(tk[0])):
	ab = list(map(int, input().split()))
	a = int(ab[0])
	b = int(ab[1])
	sm = (pre[b] - pre[a - 1] + mod) % mod
	print(sm)


def noofways_flower(n, k, dp):
	if n == 0:
		return 1
	if dp[n] != -1:
		return dp[n]
	w = 0
	if n - k >= 0:
		w = noofways_flower(n - k, k, dp)
	r = 0
	if n > 0:
		r = noofways_flower(n - 1, k, dp)
	dp[n] = (w + r) % (10 ** 9 + 7)
	return (w + r) % (10 ** 9 + 7)

def flower(k, dp, pre):
	pre[0] = 0
	for i in range(1, 10 ** 5 + 1):
		pre[i] = pre[i - 1] + noofways_flower(i, k, dp)
(t, k) = map(int, input().split())
dp = [-1 for i in range(10 ** 5 + 1)]
pre = [-1] * (10 ** 5 + 1)
flower(k, dp, pre)
for i in range(t):
	(a, b) = map(int, input().split())
	s = (pre[b] - pre[a - 1] + (10 ** 9 + 7)) % (10 ** 9 + 7)
	print(s)


(t, k) = map(int, input().split())
a = [0] * (10 ** 5 + 1)
b = [0] * (10 ** 5 + 1)
s = 0
for i in range(10 ** 5 + 1):
	if i < k:
		a[i] = 1
	else:
		a[i] = (a[i - 1] + a[i - k]) % (10 ** 9 + 7)
	s = (s + a[i]) % (10 ** 9 + 7)
	b[i] = s
for i in range(t):
	(l, r) = map(int, input().split())
	print((b[r] - b[l - 1]) % (10 ** 9 + 7))


(t, k) = map(int, input().split())
mod = 10 ** 9 + 7
q = []
m = -1
for i in range(t):
	(a, b) = map(int, input().split())
	m = max(m, b, k)
	q.append((a, b))
dp = [[0, 0, 0] for i in range(m + 1)]
dp[1][0] = 1
dp[k][1] = 1
dp[k][0] = 1
for i in range(1, m + 1):
	if i < k:
		dp[i][0] = 1
	elif i == k:
		dp[i][0] = 1
		dp[i][1] = 1
	else:
		dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod
		dp[i][1] = (dp[i][1] + dp[i - k][0] + dp[i - k][1]) % mod
	dp[i][2] = (dp[i][2] + dp[i - 1][2] + dp[i][0] + dp[i][1]) % mod
for i in q:
	a = i[0]
	b = i[1]
	x = dp[a - 1][2]
	y = dp[b][2]
	if y - x < 0:
		print(y - x + mod)
	else:
		print(y - x)


import sys
input = sys.stdin.readline
(t, k) = map(int, input().split())
mod = 10 ** 9 + 7
N = 10 ** 5 + 10
dp = [0] * N
for i in range(k):
	dp[i] = 1
for i in range(k, N):
	dp[i] = (dp[i - 1] + dp[i - k]) % mod
sdp = [dp[i] for i in range(N)]
for i in range(1, N):
	sdp[i] += sdp[i - 1]
	sdp[i] %= mod
for _ in range(t):
	(a, b) = map(int, input().split())
	print((sdp[b] - sdp[a - 1]) % mod)


(t, k) = map(int, input().split())
ways = [1] * (k - 1) + [2] + [0] * (100000 - k)
for i in range(k, 100000):
	ways[i] = (ways[i - 1] + ways[i - k]) % 1000000007
for i in range(99999):
	ways[i + 1] = (ways[i + 1] + ways[i]) % 1000000007
output = [0] * t
for i in range(t):
	(a, b) = map(int, input().split())
	output[i] = str(ways[b - 1] if a == 1 else (ways[b - 1] - ways[a - 2]) % 1000000007)
print('\n'.join(output))


M = 1000000007
l = [1] * 100005
(t, k) = map(int, input().split(' '))
for i in range(k, len(l)):
	l[i] = (l[i - 1] + l[i - k]) % M
for i in range(1, len(l)):
	l[i] = (l[i] + l[i - 1]) % M
while t > 0:
	(a, b) = map(int, input().split(' '))
	print((l[b] - l[a - 1]) % M)
	t -= 1


from math import ceil, gcd, floor
from collections import deque, defaultdict
from functools import lru_cache
from bisect import bisect_left, bisect_left, insort
from heapq import heappush as hpush, heappop as hpop
import sys
sys.setrecursionlimit(10 ** 5)
from itertools import permutations
inf = float('inf')

def inpi():
	return int(input())

def inpa():
	return list(map(int, input().split()))

def inps():
	return list(input())

def inpv():
	return map(int, input().split())
mod = 10 ** 9 + 7
(testcase, k) = inpv()
dp = [0] * (10 ** 5 + 1)
s = [0] * (10 ** 5 + 1)
dp[0] = 1
s[0] = 1
for i in range(1, 10 ** 5 + 1):
	dp[i] = (dp[i - 1] + (dp[i - k] if i >= k else 0)) % mod
	s[i] = (dp[i] + s[i - 1]) % mod
for _ in range(testcase):
	(a, b) = inpv()
	print((s[b] - s[a - 1]) % mod)


import sys
import heapq
import math
from collections import deque
from collections import defaultdict
from collections import Counter
modH = int(10 ** 9 + 7)
input = sys.stdin.readline
print = sys.stdout.write

def PRINT(lst, sep=' '):
	print(sep.join(map(str, lst)))
I = lambda : list(map(int, input().split(' ')))
(T, k) = I()
n = int(10 ** 5) + 1
dp = [None] * n
dp[0] = 0
ans = []
for i in range(1, n):
	dp[i] = ((1 + dp[i - 1] if i >= 1 else 0) % modH + (1 + dp[i - k] if i >= k else 0) % modH) % modH
PRINT(list(map(lambda x: (dp[x[1]] - dp[x[0] - 1]) % modH, [I() for _ in range(T)])), sep='\n')


MOD = 1000000007
(t, k) = [int(x) for x in input().split()]
a = []
b = []
maxi = 0
for i in range(t):
	(y, z) = [int(x) for x in input().split()]
	a.append(y)
	b.append(z)
	maxi = max(maxi, z, y)
dp = [0]
f = [0]
sum = 0
for i in range(1, maxi + 2):
	if i < k:
		plus = 1
	elif i == k:
		plus = 2
	elif i > k:
		plus = (dp[i - 1] + dp[i - k]) % MOD
	dp.append(plus)
	sum += plus % MOD
	f.append(sum)
for i in range(t):
	if a[i] != b[i]:
		print((f[b[i]] - f[a[i] - 1]) % MOD)
	else:
		print(dp[b[i]])


from __future__ import division, print_function
import itertools, os, sys, threading
from collections import deque, Counter, OrderedDict, defaultdict
import heapq
from math import ceil, floor, log, sqrt, factorial, pow, pi

def ii():
	return int(input())

def si():
	return str(input())

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def getKey(item):
	return item[0]

def sort2(l):
	return sorted(l, key=getKey)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
graph = defaultdict(list)
visited = [0] * 1000000
col = [-1] * 1000000

def dfs(v, c):
	if visited[v]:
		if col[v] != c:
			print('-1')
			exit()
		return
	col[v] = c
	visited[v] = 1
	for i in graph[v]:
		dfs(i, c ^ 1)

def bfs(d, v):
	q = []
	q.append(v)
	visited[v] = 1
	while len(q) != 0:
		x = q[0]
		q.pop(0)
		for i in d[x]:
			if visited[i] != 1:
				visited[i] = 1
				q.append(i)
		print(x)
	print(l)

def make_graph(e):
	d = {}
	for i in range(e):
		(x, y) = mi()
		if x not in d.keys():
			d[x] = [y]
		else:
			d[x].append(y)
		if y not in d.keys():
			d[y] = [x]
		else:
			d[y].append(x)
	return d

def gr2(n):
	d = {}
	for i in range(n):
		(x, y) = mi()
		if x not in d.keys():
			d[x] = [y]
		else:
			d[x].append(y)
	return d

def connected_components(graph):
	seen = set()

	def dfs(v):
		vs = set([v])
		component = []
		while vs:
			v = vs.pop()
			seen.add(v)
			vs |= set(graph[v]) - seen
			component.append(v)
		return component
	ans = []
	for v in graph:
		if v not in seen:
			d = dfs(v)
			ans.append(d)
	return ans
(t, k) = mi()
dp = [0] * (10 ** 5 + 1)
dp[0] = 1
for i in range(10 ** 5):
	dp[i + 1] = (dp[i + 1] + dp[i]) % 1000000007
	if i + k < 100001:
		dp[i + k] = (dp[i + k] + dp[i]) % 1000000007
s = [0] * (10 ** 5 + 2)
for i in range(10 ** 5 + 1):
	s[i + 1] = (s[i] + dp[i]) % 1000000007
for i in range(t):
	(a, b) = mi()
	print((s[b + 1] + 1000000007 - s[a]) % 1000000007)


(t, k) = map(int, input().split())
MX = 100005
MOD = 1000000007
dp_ans = [0 for i in range(MX)]
dp_ans[0] = 1
for i in range(1, MX):
	dp_ans[i] += dp_ans[i - 1]
	if i - k >= 0:
		dp_ans[i] += dp_ans[i - k]
	dp_ans[i] %= MOD
dp = [0 for i in range(MX)]
dp[0] = dp_ans[0]
for i in range(1, MX):
	dp[i] = dp[i - 1] + dp_ans[i]
	dp[i] %= MOD
for i in range(t):
	(a, b) = map(int, input().split())
	ans = dp[b] - dp[a - 1] + 2 * MOD
	ans %= MOD
	print(ans)


special = 1000000007

def process(lines, max_num, k):
	dp = [1] * (max_num + 1)
	for i in range(1, k):
		dp[i] = 1
	dp[k] = 2
	for i in range(k + 1, max_num + 1):
		dp[i] = (dp[i - 1] % special + dp[i - k] % special) % special
	sum = [0] * (max_num + 1)
	for i in range(1, max_num + 1):
		sum[i] = (dp[i] + sum[i - 1]) % special
	res = []
	for pair in lines:
		cur = (sum[pair[1]] - sum[pair[0] - 1] + special) % special
		res.append(cur)
	return res
line = input().strip().split()
(t, k) = map(int, line)
lines = []
max_num = 0
for i in range(t):
	nums = list(map(int, input().strip().split()))
	max_num = max(max_num, nums[1])
	lines.append(nums)
res = process(lines, max_num, k)
print('\n'.join(list(map(str, res))))


MOD = 1000000007
(t, k) = map(int, input().split())
queries = list()
b_max = -1000000000
for _ in range(t):
	(a, b) = map(int, input().split())
	queries.append((a, b))
	b_max = max(b, b_max)
dp = dict()
for i in range(0, b_max + 2):
	if i < k:
		dp[i] = 1
	else:
		dp[i] = (dp[i - 1] % MOD + dp[i - k] % MOD) % MOD
cum_sum = [0]
curr_sum = 0
for (i, ways) in dp.items():
	if i > 0:
		curr_sum += dp[i]
		cum_sum.append(curr_sum)
for query in queries:
	(a, b) = query
	print((cum_sum[b] - cum_sum[a - 1]) % MOD)


(t, k) = map(int, input().split())
m = int(1000000000.0) + 7
dp = [x for x in range(1, k + 1)]
for i in range(k, 100001):
	dp.append((dp[i - 1] + dp[i - k] + 1) % m)
for _ in range(t):
	(a, b) = map(int, input().split())
	print((dp[b] - dp[a - 1]) % m)


def flowers(k):
	for i in range(1, 100005):
		if i < k:
			dp[i] = dp[i - 1]
		else:
			dp[i] = (dp[i - 1] % (10 ** 9 + 7) + dp[i - k] % (10 ** 9 + 7)) % (10 ** 9 + 7)
	for i in range(1, 100005):
		dp[i] = dp[i - 1] % (10 ** 9 + 7) + dp[i] % (10 ** 9 + 7)
(t, k) = map(int, input().split())
dp = [1 for i in range(100005)]
flowers(k)
for _ in range(t):
	(n, s) = map(int, input().split())
	print((dp[s] - dp[n - 1] + (10 ** 9 + 7)) % (10 ** 9 + 7))


def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
M = 10 ** 9 + 7

def solve():
	(A, B) = getInts()
	return (dp_sum[B] - dp_sum[A - 1]) % M
(T, K) = getInts()
dp = [[0 for j in range(2)] for i in range(10 ** 5 + 1)]
dp[0][0] = 1
dp[0][1] = 0
dp_sum = {0: 1}
sum_dp = 1
for i in range(1, K):
	dp[i][0] = 1
	sum_dp += 1
	dp_sum[i] = sum_dp
for i in range(K, 10 ** 5 + 1):
	(AA, BB, CC, DD) = (dp[i - K][0], dp[i - K][1], dp[i - 1][0], dp[i - 1][1])
	AB = (AA + BB) % M
	CD = (CC + DD) % M
	dp[i][1] = AB % M
	dp[i][0] = CD % M
	sum_dp += AB + CD
	sum_dp %= M
	dp_sum[i] = sum_dp
for t in range(T):
	ans = solve()
	print(ans)


(t, k) = map(int, input().split(' '))
ans = [0]
for i in range(k - 1):
	ans.append(1)
ans.append(2)
for j in range(len(ans), 10 ** 5 + 1):
	ans.append((ans[j - k] + ans[j - 1]) % 1000000007)
for i in range(1, len(ans)):
	ans[i] = (ans[i] + ans[i - 1]) % 1000000007
while t:
	(a, b) = map(int, input().split(' '))
	print((ans[b] - ans[a - 1]) % 1000000007)
	t = t - 1


from sys import stdin, stdout
lines = list([_f for _f in stdin.read().split('\n') if _f])

def parseline(line):
	return list(map(int, line.split()))
lines = list(map(parseline, lines))
(t, k) = lines[0]
assert len(lines) >= t + 1
max_flowers = 10 ** 5
modulo = 10 ** 9 + 7
A = [0] * (1 + max_flowers)
A[0] = 1
A_sum = [0] * (1 + max_flowers)
for i in range(1, 1 + max_flowers):
	Ai_m_k = A[i - k] if i >= k else 0
	A[i] = (A[i - 1] + Ai_m_k) % modulo
	A_sum[i] = (A_sum[i - 1] + A[i]) % modulo

def tests():
	for i in range(1, t + 1):
		yield lines[i]
for (a, b) in tests():
	print((A_sum[b] - A_sum[a - 1]) % modulo)


(t, k) = map(int, input().split())
p = 10 ** 9 + 7
dp = [0 for i in range(10 ** 5 + 1)]
for i in range(10 ** 5 + 1):
	if i < k:
		dp[i] = 1
	else:
		dp[i] = (dp[i - 1] + dp[i - k]) % p
dp[0] = 0
prefix = []
prefix.append(dp[0])
for i in range(1, 10 ** 5 + 1):
	prefix.append((prefix[-1] + dp[i]) % p)
while t:
	(a, b) = map(int, input().split())
	print((prefix[b] - prefix[a - 1] + p) % p)
	t -= 1


mod = 10 ** 9 + 7

def main():
	(t, k) = map(int, input().split())
	dp = [0] * (10 ** 5 + 1)
	for i in range(k):
		dp[i] = 1
	for i in range(k, 10 ** 5 + 1):
		dp[i] = (dp[i - 1] + dp[i - k]) % mod
	for i in range(1, 10 ** 5 + 1):
		dp[i] = (dp[i] + dp[i - 1]) % mod
	for _ in range(t):
		(a, b) = map(int, input().split())
		print((dp[b] - dp[a - 1]) % mod)
main()


(q, f) = map(int, input().split())
dp = [1 for i in range(f)]
mod = 10 ** 9 + 7
for i in range(100004):
	dp.append((dp[-1] + dp[-f]) % mod)
dp[0] = 0
for i in range(1, len(dp)):
	dp[i] = (dp[i] + dp[i - 1]) % mod
ans = ''
for i in range(q):
	(a, b) = map(int, input().split())
	ans += str((dp[b] - dp[a - 1]) % mod) + chr(10)
print(ans)


def ds(a, b, c):
	if a == 0:
		m = 0
		while m < len(c):
			e = 0
			while m < len(c) and c[m]:
				m += 1
				e += 1
			if e % b:
				return 0
			m += 1
		return 1
	return ds(a - 1, b, c + [0]) + ds(a - 1, b, c + [1])
(t, k) = map(int, input().split())
m = 10 ** 5 + 1
mod = 10 ** 9 + 7
de = [1] * m
for i in range(1, m):
	de[i] = de[i - 1]
	if i - k >= 0:
		de[i] = (de[i] + de[i - k]) % mod
de[0] = 0
d = [0] * m
for i in range(1, m):
	d[i] = (de[i] + d[i - 1]) % mod
for _ in range(t):
	(a, b) = map(int, input().split())
	print((d[b] - d[a - 1]) % mod)


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())
(t, k) = mints()
dp = [0] * (10 ** 5 + 1)
dp[0] = 1
for i in range(10 ** 5):
	dp[i + 1] = (dp[i + 1] + dp[i]) % 1000000007
	if i + k < 100001:
		dp[i + k] = (dp[i + k] + dp[i]) % 1000000007
s = [0] * (10 ** 5 + 2)
for i in range(10 ** 5 + 1):
	s[i + 1] = (s[i] + dp[i]) % 1000000007
for i in range(t):
	(a, b) = mints()
	print((s[b + 1] + 1000000007 - s[a]) % 1000000007)


(t, k) = map(int, input().split())
dp = []
mod = 1000000007
dp.append(1)
for i in range(1, 100006):
	if i < k:
		dp.append(dp[i - 1])
	else:
		dp.append((dp[i - 1] % mod + dp[i - k] % mod) % mod)
for i in range(1, 100006):
	dp[i] = (dp[i - 1] % mod + dp[i] % mod) % mod
for _ in range(t):
	(a, b) = map(int, input().split())
	print((dp[b] - dp[a - 1] + mod) % mod)


import sys
bil = 1000000007
up = 100000
dp = [0 for _ in range(100001)]

def dynamic(k):
	for i in range(1, up + 1):
		if i - k >= 0:
			dp[i] = (dp[i - k] + 1 + dp[i - 1] + 1 + bil) % bil
		else:
			dp[i] = (dp[i - 1] + 1 + bil) % bil
(t, k) = map(int, input().split())
dynamic(k)
for _ in range(t):
	(a, b) = map(int, input().split())
	print((dp[b] - dp[a - 1] + bil) % bil)


(n, k) = [int(x) for x in input().split()]
dp = [1] * k
for i in range(k, 100000 + 1):
	dp.append((dp[i - 1] + dp[i - k]) % 1000000007)
par = [1]
for i in range(1, 100000 + 1):
	par.append(par[i - 1] + dp[i])
for i in range(n):
	(a, b) = [int(x) for x in input().split()]
	print((par[b] - par[a - 1] + 1000000007) % 1000000007)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
mod = 1000000007
INF = float('inf')
Y = 'YES'
N = 'NO'
(ts, k) = mp()
dp = [i for i in range(1, k + 1)]
for i in range(k, 100001):
	dp.append((dp[i - 1] + dp[i - k] + 1) % mod)
for t in range(ts):
	(a, b) = mp()
	print((dp[b] - dp[a - 1]) % mod)


tk = input().strip('\n').split()
t = int(tk[0])
k = int(tk[1])
test = []
for _ in range(t):
	ab = input().strip('\n').split()
	a = int(ab[0])
	b = int(ab[1])
	test.append([a, b])
way_memo = [None for _ in range(100001)]
for i in range(k):
	way_memo[i] = 1
for i in range(k, len(way_memo)):
	way_memo[i] = (way_memo[i - k] + way_memo[i - 1]) % 1000000007
sum = [0 for _ in range(100001)]
for i in range(1, 100001):
	sum[i] = (sum[i - 1] + way_memo[i]) % 1000000007
for i in range(t):
	a = test[i][0]
	b = test[i][1]
	print((sum[b] - sum[a - 1] + 1000000007) % 1000000007)


(tc, k) = map(int, input().split())
MAXM = 100005
MOD = 1000000007
dp = [1 for _ in range(MAXM)]
for i in range(k, MAXM):
	dp[i] = (dp[i - 1] + dp[i - k]) % MOD
for i in range(1, MAXM):
	dp[i] += dp[i - 1]
for i in range(tc):
	(a, b) = map(int, input().split())
	print((dp[b] - dp[a - 1]) % MOD)


import math
import time
from collections import defaultdict, deque
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
MOD = 1000000007
(t, k) = map(int, stdin.readline().split())
dp = defaultdict(lambda : 0)
dp[0] = 1
prefixsum = defaultdict(lambda : 0)
for i in range(1, 100001):
	dp[i] = dp[i - 1] + dp[i - k]
	dp[i] %= MOD
	prefixsum[i] = dp[i] + prefixsum[i - 1]
for _ in range(t):
	(a, b) = map(int, stdin.readline().split())
	ans = 0
	print((prefixsum[b] - prefixsum[a - 1]) % MOD)


def main():
	mod = 10 ** 9 + 7
	(t, k) = map(int, input().split())
	dp = [0]
	for i in range(k - 1):
		dp.append(1)
	dp.append(2)
	for i in range(pow(10, 5) + 1 - k):
		dp.append(dp[-1] + dp[-k])
		dp[-1] %= mod
	for i in range(1, len(dp)):
		dp[i] += dp[i - 1]
		dp[i] %= mod
	ans = []
	for i in range(t):
		(a, b) = map(int, input().split())
		ans.append(dp[b] - dp[a - 1])
		ans[-1] %= mod
	for i in ans:
		print(i)
main()


(t, k) = map(int, input().split())
N = 1000000007
nl = [1] * k
sl = [0]
for i in range(k - 1):
	sl.append((sl[-1] + 1) % N)
for i in range(k, 10 ** 5 + 1):
	nl.append((nl[-k] + nl[-1]) % N)
	sl.append((sl[-1] + nl[-1]) % N)
for _ in range(t):
	(a, b) = map(int, input().split())
	print((sl[b] - sl[a - 1]) % N)


m = 1000000007
(t, k) = map(int, input().split())
a = [0] * 100001
a[:k] = [1] * k
for i in range(k, 100001):
	a[i] = (a[i - 1] + a[i - k]) % m
for i in range(1, 100001):
	a[i] = (a[i - 1] + a[i]) % m
for i in range(t):
	(x, y) = map(int, input().split())
	print((a[y] - a[x - 1]) % m)


MOD = 1000000007
SIZE = 100010
dp = [-1 for i in range(SIZE)]

def flowers(n, k):
	if n == 0:
		return 1
	if dp[n] != -1:
		return dp[n]
	temp = 0
	if n >= k:
		temp = flowers(n - k, k) % MOD
	temp += flowers(n - 1, k) % MOD
	temp %= MOD
	dp[n] = temp
	return dp[n]

def flowers_runner():
	dp[0] = 0
	line = input()
	(sn, sk) = line.split(' ')
	n = int(sn)
	k = int(sk)
	for i in range(SIZE - 1):
		flowers(i + 1, k)
	for i in range(SIZE - 1):
		dp[i + 1] += dp[i]
		dp[i + 1] %= MOD
	while n != 0:
		line = input()
		(sa, sb) = line.split(' ')
		a = int(sa)
		b = int(sb)
		print((MOD + dp[b] - dp[a - 1]) % MOD)
		n -= 1
flowers_runner()


import sys
MOD = 1000000007

def main():
	iter_data = map(int, sys.stdin.read().split())
	(t, k) = (next(iter_data), next(iter_data))
	all_tests = list(iter_data)
	max_n = max(all_tests)
	dp = [0] * (max_n + 1)
	dp[:k] = [1] * k
	for i in range(k, max_n + 1):
		dp[i] = (dp[i - 1] + dp[i - k]) % MOD
	p_sum = [0] * (max_n + 1)
	cur_val = 0
	for i in range(max_n + 1):
		p_sum[i] = cur_val = cur_val + dp[i]
	ans = [0] * t
	for t_id in range(t):
		(a, b) = all_tests[t_id * 2:t_id * 2 + 2]
		ans[t_id] = (p_sum[b] - p_sum[a - 1]) % MOD
	print(*ans, sep='\n')
main()


(t, k) = map(int, input().split())
mod = 10 ** 9 + 7
dp = [0] * (10 ** 5 + 1)
for i in range(k):
	dp[i] = 1
for i in range(k, 10 ** 5 + 1):
	dp[i] = (dp[i - k] + dp[i - 1]) % mod
for i in range(1, 10 ** 5 + 1):
	dp[i] += dp[i - 1]
	dp[i] %= mod
for _ in range(t):
	(l, r) = map(int, input().split())
	print((dp[r] - dp[l - 1]) % mod)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from heapq import *
from math import gcd, factorial, floor, ceil
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 10 ** 9 + 7

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def solve(case):
	(q, k) = sep()
	dp = [0] * (10 ** 5 + 1)
	for i in range(k):
		dp[i] = 1
	for i in range(k, 10 ** 5 + 1):
		dp[i] = dp[i - 1] + dp[i - k]
		dp[i] %= mod
	for i in range(1, 10 ** 5 + 1):
		dp[i] += dp[i - 1]
		dp[i] %= mod
	for i in range(q):
		(a, b) = sep()
		print((dp[b] - dp[a - 1]) % mod)
testcase(1)


tk = input().strip('\n').split(' ')
t = int(tk[0])
k = int(tk[1])
data = [1] * k
for i in range(k, 100001):
	data.append((data[i - k] + data[i - 1]) % 1000000007)
for i in range(1, 100001):
	data[i] += data[i - 1]
	data[i] %= 1000000007
while t > 0:
	t = t - 1
	ab = [int(i) for i in input().strip('\n').split(' ')]
	ans = data[ab[1]] - data[ab[0] - 1] + 1000000007
	ans %= 1000000007
	print(ans)


(cases, k) = map(int, input().strip().split())
total = 100001
mod_num = 10 ** 9 + 7
dp = [0] * total
dp[0] = 1
for i in range(1, total):
	temp = dp[i - k] if i >= k else 0
	dp[i] = (dp[i - 1] + temp) % mod_num
sums = [0] * total
t = 0
for i in range(1, total):
	sums[i] = (sums[i - 1] + dp[i]) % mod_num
for _ in range(cases):
	(a, b) = map(int, input().strip().split())
	print((sums[b] - sums[a - 1] + mod_num) % mod_num)


dp = [-1] * 100001

def cmp(n, k, m):
	ct = 0
	if n == 0:
		return 1
	if dp[n] != -1:
		return dp[n]
	if n >= k:
		ct += cmp(n - k, k, m)
		ct %= m
	ct += cmp(n - 1, k, m)
	ct %= m
	dp[n] = ct
	return ct
ans = [0] * 100001
(t, k) = map(int, input().split())

def prefixSum():
	for i in range(1, 10 ** 5 + 1):
		ans[i] = ans[i - 1] + cmp(i, k, 10 ** 9 + 7)
		ans[i] %= 10 ** 9 + 7
prefixSum()
for i in range(t):
	(a, b) = map(int, input().split())
	val = (ans[b] - ans[a - 1]) % (10 ** 9 + 7)
	print(val)


n = 10 ** 5 + 1
mod = 10 ** 9 + 7
(t, k) = map(int, input().split())
(a, b) = ([1] * n, [0] * n)
j = 0
for i in range(n):
	if i < k:
		b[i] = i + 1
	else:
		a[i] = (a[j] + a[i - 1]) % mod
		b[i] = (b[i - 1] + a[i]) % mod
		j += 1
for _ in range(t):
	(u, v) = map(int, input().split())
	print((b[v] - b[u - 1]) % mod)


from sys import setcheckinterval, stdin, setrecursionlimit
setcheckinterval(1000)
setrecursionlimit(10 ** 7)

def iin():
	return int(stdin.readline())

def lin():
	return list(map(int, stdin.readline().split()))
(n, k) = lin()
md = 10 ** 9 + 7
dp = [0 for i in range(10 ** 5 + 1)]
dp[1] = 1 + (1 if k == 1 else 0)
for i in range(2, 10 ** 5 + 1):
	dp[i] += dp[i - 1]
	if i >= k:
		if dp[i - k]:
			dp[i] += dp[i - k]
		else:
			dp[i] += 1
	dp[i] %= md
for i in range(1, 10 ** 5 + 1):
	dp[i] += dp[i - 1]
	dp[i] %= md
for i in range(n):
	(a, b) = lin()
	print((dp[b] - dp[a - 1]) % md)


(t, k) = map(int, input().split())
mod = 10 ** 9 + 7
end = 10 ** 5 + 1
dp = [1] * end
for i in range(k, end):
	dp[i] = dp[i - 1] + dp[i - k]
	if dp[i] >= mod:
		dp[i] %= mod
for i in range(1, end):
	dp[i] += dp[i - 1]
	if dp[i] >= mod:
		dp[i] %= mod
for _ in range(t):
	(a, b) = map(int, input().split())
	print((dp[b] - dp[a - 1]) % mod)


import sys, io, os, time
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect, math, heapq
alphabet = 'abcdefghijklmnopqrstuvwxyz'
input = sys.stdin.readline
import collections, sys, threading
sys.setrecursionlimit(10 ** 9)
threading.stack_size(10 ** 8)

def solve():
	(t, k) = map(int, input().split())
	nax = 10 ** 5 + 5
	dp = [-1] * nax
	mod = 10 ** 9 + 7
	dp[0] = 0

	def f(currflow):
		if currflow == 0:
			return 1
		if currflow < 0:
			return 1
		if dp[currflow] != -1:
			return dp[currflow]
		ans = 0
		ans += f(currflow - 1)
		ans %= mod
		if currflow - k >= 0:
			ans += f(currflow - k)
			ans %= mod
		dp[currflow] = ans
		return dp[currflow]
	pref_sum = [0]
	for i in range(nax):
		if dp[i] == -1:
			f(i)
		pref_sum.append(pref_sum[-1] + dp[i])
	for ii in range(t):
		(a, b) = map(int, input().split())
		print((pref_sum[b + 1] - pref_sum[a]) % mod)
threading.Thread(target=solve).start()


from sys import stdin, stdout
(t, k) = stdin.readline().split()
t = int(t)
k = int(k)
dp = [[0 for i in range(2)] for j in range(100005)]
dp[0][0] = 1
dp[0][1] = 1
mod = 1000000007
for i in range(100005):
	dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod
	if i - k >= 0:
		dp[i][1] = (dp[i - k][0] + dp[i - k][1]) % mod
ans = [0 for i in range(100005)]
for i in range(1, 100005):
	ans[i] = (ans[i - 1] + dp[i][0] + dp[i][1]) % mod
for i in range(t):
	x = tuple(map(int, stdin.readline().split()))
	an = ans[x[1]] - ans[x[0] - 1]
	if an < 0:
		an += mod
	stdout.write(str(an) + '\n')


def read_int():
	return int(input().strip())

def read_ints():
	return list(map(int, input().strip().split(' ')))

def solve():
	(t, k) = read_ints()
	modulo = 10 ** 9 + 7
	OPT = [0 for _ in range(10 ** 5 + 1)]
	OPT[0] = 1
	for i in range(1, 10 ** 5 + 1):
		OPT[i] = OPT[i - 1]
		if i - k >= 0:
			OPT[i] = (OPT[i] + OPT[i - k]) % modulo
	for i in range(1, 10 ** 5 + 1):
		OPT[i] = (OPT[i] + OPT[i - 1]) % modulo
	for _ in range(t):
		(a, b) = read_ints()
		print((OPT[b] - OPT[a - 1]) % modulo)
solve()


(t, k) = list(map(int, input().split()))
dp = [1] * (100000 + 1)
mod = int(1000000000.0 + 7)
for i in range(k, 100000 + 1):
	dp[i] = (dp[i - k] + dp[i - 1] + mod) % mod
for i in range(1, 100000 + 1):
	dp[i] += dp[i - 1] + mod
	dp[i] = dp[i] % mod
for _ in range(t):
	(a, b) = list(map(int, input().split()))
	result = (dp[b] - dp[a - 1] + mod) % mod
	print(result)


(t, k) = [int(x) for x in input().split()]
mod = 10 ** 9 + 7
dp = [0] * 100002
dp[0] = 1
for i in range(1, 100002):
	dp[i] = dp[i - 1]
	if i >= k:
		dp[i] += dp[i - k]
		dp[i] %= mod
ans = [0]
for i in dp[1:]:
	ans.append((ans[-1] + i) % mod)
for i in range(t):
	(l, r) = [int(x) for x in input().split()]
	val = ans[r] - ans[l - 1]
	if val < 0:
		val += mod
	print(val % mod)


import time, math as mt, bisect as bs, sys
from sys import stdin, stdout
from collections import deque
from fractions import Fraction
from collections import Counter
from collections import OrderedDict
pi = 3.141592653589793

def II():
	return int(stdin.readline())

def IO():
	return stdin.readline()

def IP():
	return map(int, stdin.readline().split())

def L():
	return list(map(int, stdin.readline().split()))

def P(x):
	return stdout.write(str(x) + '\n')

def PI(x, y):
	return stdout.write(str(x) + ' ' + str(y) + '\n')

def lcm(a, b):
	return a * b // gcd(a, b)

def gcd(a, b):
	if a == 0:
		return b
	elif b == 0:
		return a
	if a > b:
		return gcd(a % b, b)
	else:
		return gcd(a, b % a)

def readTree():
	v = int(input())
	adj = [set() for i in range(v + 1)]
	for i in range(v - 1):
		(u1, u2) = In()
		adj[u1].add(u2)
		adj[u2].add(u1)
	return (adj, v)

def bfs(adj, v):
	visited = [False] * (v + 1)
	q = deque()
	while q:
		pass

def sieve():
	li = [True] * 1000001
	(li[0], li[1]) = (False, False)
	for i in range(2, len(li), 1):
		if li[i] == True:
			for j in range(i * i, len(li), i):
				li[j] = False
	prime = []
	for i in range(1000001):
		if li[i] == True:
			prime.append(i)
	return prime

def setBit(n):
	count = 0
	while n != 0:
		n = n & n - 1
		count += 1
	return count
mx = 10 ** 7
spf = [mx] * (mx + 1)

def SPF():
	spf[1] = 1
	for i in range(2, mx + 1):
		if spf[i] == mx:
			spf[i] = i
			for j in range(i * i, mx + 1, i):
				if i < spf[j]:
					spf[j] = i
	return
mod = 10 ** 9 + 7

def solve():
	(t, k) = IP()
	mx = 10 ** 5 + 1
	mod = 10 ** 9 + 7
	dp = [[0, 0] for i in range(mx)]
	dp[1][0] = 1
	dp[k][1] = 1
	for i in range(1, mx):
		dp[i][0] += (dp[i - 1][1] + dp[i - 1][0]) % mod
		x = max(i - k, 0)
		dp[i][1] += (dp[x][1] + dp[x][0]) % mod
	pref = [0] * mx
	pref[1] = (dp[1][0] + dp[1][1]) % mod
	for i in range(2, mx):
		pref[i] += (pref[i - 1] + dp[i][0] + dp[i][1]) % mod
	for i in range(t):
		(a, b) = IP()
		print((pref[b] - pref[a - 1]) % mod)
	return
t = 1
for i in range(t):
	solve()


(t, k) = map(int, input().split())
m = 1000000007
lis = [1] * k
s = [0]
for i in range(k, 100001):
	lis.append((lis[i - 1] + lis[i - k]) % m)
for i in lis:
	s.append((i + s[-1]) % m)
for _ in range(t):
	(a, b) = map(int, input().split())
	print((s[b + 1] - s[a]) % m)


(t, k) = [int(x) for x in input().split()]
a_b_values = [tuple((int(x) for x in input().split())) for _ in range(t)]
max_b = max(a_b_values, key=lambda i: i[1])[1]
ways = [None] * (max_b + 1)
sum_ways = [None] * (max_b + 1)
mod = 10 ** 9 + 7
for i in range(k):
	ways[i] = 1
	if i == 0:
		sum_ways[i] = 0
	else:
		sum_ways[i] = sum_ways[i - 1] + 1
for i in range(k, max_b + 1):
	ways[i] = ways[i - 1] + ways[i - k]
	if ways[i] > mod:
		ways[i] -= mod
	sum_ways[i] = ways[i] + sum_ways[i - 1]
	if sum_ways[i] > mod:
		sum_ways[i] -= mod
for (a, b) in a_b_values:
	total = sum_ways[b] - sum_ways[a - 1]
	if total < 0:
		total += mod
	print(total)


def main():
	(t, k) = map(int, input().split())
	max_n = 100003
	mod = 1000000007
	d = [1] * max_n
	for i in range(k, max_n):
		d[i] = (d[i - 1] + d[i - k]) % mod
	for i in range(1, max_n):
		d[i] = (d[i] + d[i - 1]) % mod
	for i in range(t):
		(a, b) = map(int, input().split())
		print((d[b] - d[a - 1]) % mod)
main()


inp = lambda : map(int, input().rstrip().split())
(t, k) = inp()
mod = 1000000007
dp = [x for x in range(1, k + 1)]
for i in range(k, 100002):
	dp.append((dp[i - 1] + dp[i - k] + 1) % mod)
for _ in range(t):
	(a, b) = inp()
	print((dp[b] - dp[a - 1]) % mod)


from sys import stdin
mx = 10 ** 5 + 1
(t, k) = list(map(int, stdin.readline().split()))
dp = [1] * mx
dp[0] = 0
dp[k] = 2
for i in range(k + 1, mx):
	dp[i] = (dp[i - 1] + dp[i - k]) % (10 ** 9 + 7)
cum = [0] * mx
for i in range(1, mx):
	cum[i] = (cum[i - 1] + dp[i]) % (10 ** 9 + 7)
for _ in range(t):
	(a, b) = list(map(int, stdin.readline().split()))
	print((cum[b] - cum[a - 1]) % (10 ** 9 + 7))


import sys
input = sys.stdin.readline
MOD = 1000000007
MOD2 = 998244353
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input().strip('\n'))
let = 'abcdefghijklmnopqrstuvwxyz'
N = 10 ** 5 + 1
(t, k) = f()
dp = [1] * N
dpsm = [0] * N
dpsm[0] = 1
for i in range(k, N):
	dp[i] = (dp[i - 1] + dp[i - k]) % MOD
for i in range(1, N):
	dpsm[i] = (dpsm[i - 1] + dp[i]) % MOD
for _ in range(t):
	(a, b) = f()
	print((dpsm[b] - dpsm[a - 1]) % MOD)


(t, k) = map(int, input().split())
mod = 1000000007
maxb = 0
nr = [0] * 100005
psum = [0] * 100005
nr[0] = 1
for r in range(100004):
	i = r + 1
	nr[i] = nr[i - 1]
	if i >= k:
		nr[i] = (nr[i] + nr[i - k]) % mod
	psum[i] = (psum[i - 1] + nr[i]) % mod
for xfr in range(t):
	(a, b) = map(int, input().split())
	print((psum[b] - psum[a - 1]) % mod)


(t, k) = map(int, input().strip().split(' '))
q = []
mx = 0
while t:
	t -= 1
	(a, b) = map(int, input().strip().split(' '))
	mx = max(mx, b)
	q.append([a, b])
dp = [0] * (mx + 1)
for i in range(0, k):
	dp[i] = 1
dp[k] = 2
for i in range(k + 1, mx + 1):
	dp[i] = dp[i - 1] + dp[i - k]
	dp[i] %= 10 ** 9 + 7
for i in range(1, mx + 1):
	dp[i] = (dp[i - 1] + dp[i]) % (10 ** 9 + 7)
for z in q:
	print((dp[z[1]] - dp[z[0] - 1]) % (10 ** 9 + 7))


(t, k) = map(int, input().split())
dp = [1]
for i in range(1, k):
	dp.append(1)
dp.append(2)
for i in range(k + 1, 100001):
	a = dp[i - 1] + dp[i - k]
	dp.append(a % 1000000007)
for i in range(1, 100001):
	dp[i] += dp[i - 1]
for _ in range(t):
	(a, b) = map(int, input().split())
	ans = (dp[b] - dp[a - 1]) % 1000000007
	if ans < 0:
		ans += 1000000007
	print(ans)


import sys
import collections
import math
import functools
import itertools
import bisect
import operator
import heapq
import random
true = True
false = False
null = None
SLOW = True
memoi = functools.lru_cache(None)
tcid = 0
tcmax = 99999999
mod = 10 ** 9 + 7

def fast():
	SLOW = False

def compute(val, func):
	return func(val)

def seq(lo, hi, step=1):
	return range(lo, hi + 1, step)

def sround(val, nd):
	return f'{val:.{nd}f}'

def ceil(a, b):
	ans = a // b
	if a % b != 0:
		ans += 1
	return ans

def perr(*args, **kwargs):
	if SLOW:
		print(*args, file=sys.stderr, **kwargs)

def line():
	ln = sys.stdin.readline().strip()
	if ln == '':
		sys.exit()
	return ln

def lines(n):
	return [line() for i in range(n)]

def split(ln=None):
	return (ln or line()).split()

def num(str=None):
	str = str or line()
	return float(str) if '.' in str else int(str)

def nums(o=None):
	if o is not None:
		if isinstance(o, int):
			o = lines(o)
		elif isinstance(o, str):
			o = split(o)
	return list(map(num, o or split()))
(tcmax, k) = nums()

@memoi
def aaa(nn):
	if nn == 0:
		return 1
	ans = aaa(nn - 1)
	if nn >= k:
		ans = (ans + aaa(nn - k)) % mod
	return ans

@memoi
def bbb(nn):
	if nn == 0:
		return 0
	ans = (aaa(nn) + bbb(nn - 1)) % mod
	return ans
for nn in range(0, 99999, 99):
	bbb(nn)

def mainloop(tcid=1):
	(a, b) = nums()
	ans = (mod + bbb(b) - bbb(a - 1)) % mod
	print(ans)
while tcid < tcmax:
	tcid += 1
	mainloop(tcid)


s = input().split()
t = int(s[0])
k = int(s[1])
nr = [1 for i in range(k)]
sums1 = [i for i in range(k)]
sums2 = [0 for i in range(100001 - k)]
sums = sums1 + sums2
for j in range(k, 100001):
	nr[j % k] += nr[(j - 1) % k] % 1000000007
	sums[j] = (sums[j - 1] + nr[j % k]) % 1000000007
for i in range(t):
	s = input().split()
	a = int(s[0])
	b = int(s[1])
	res = sums[b] - sums[a - 1]
	print(res % 1000000007)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
(t, k) = map(int, input().split())
mod = 10 ** 9 + 7
a = 10 ** 5 + 1
dp = [0] * a
dp[0] = 1
for i in range(1, a):
	if i < k:
		dp[i] = 1
	else:
		dp[i] = (dp[i - 1] % mod + dp[i - k] % mod) % mod
sum = [0] * a
for i in range(1, a):
	sum[i] = (dp[i] % mod + sum[i - 1] % mod) % mod
for i in range(t):
	(a, b) = map(int, input().split())
	print((sum[b] - sum[a - 1]) % mod)


(t, k) = map(int, input().split())
mod = 10 ** 9 + 7
x = []
for i in range(t):
	(a, b) = map(int, input().split())
	x.append([a - 1, b])
dp = [0 for i in range(100004)]
dp[0] = 1
for i in range(1, 100001):
	if i >= k:
		dp[i] = (dp[i - 1] + dp[i - k]) % mod
	else:
		dp[i] = dp[i - 1] % mod
for i in range(1, 100002):
	dp[i] = (dp[i] + dp[i - 1]) % mod
for i in x:
	print((dp[i[1]] - dp[i[0]]) % mod)


m = 10 ** 5
mod = 10 ** 9 + 7
(t, k) = map(int, input().split())
l = [1] * (m + 1)
(l[0], l[k]) = (0, 2)
for i in range(k + 1, m + 1):
	l[i] = (l[i - 1] + l[i - k]) % mod
for i in range(1, m + 1):
	l[i] = (l[i - 1] + l[i]) % mod
for i in range(t):
	(a, b) = map(int, input().split())
	print((l[b] - l[a - 1]) % mod)


(t, k) = map(int, input().split())
A = [0]
B = [0]
bmax = 0
m = 1000000007
for _ in range(t):
	(a, b) = map(int, input().split())
	A += [a]
	B += [b]
	bmax = max(bmax, b)
arr = [0] * (bmax + 1)
for i in range(bmax + 1):
	if i < k:
		arr[i] = 1
	else:
		arr[i] = (arr[i - 1] % m + arr[i - k] % m) % m
for i in range(bmax + 1):
	if i != 0:
		arr[i] = (arr[i - 1] % m + arr[i] % m) % m
for i in range(1, t + 1):
	print((arr[B[i]] % m - arr[A[i] - 1] % m) % m)


(t, k) = map(int, input().split())
dp = [0 for x in range(100001)]
for x in range(1, k + 1):
	dp[x] = 1
dp[k] += 1
for x in range(k + 1, 100001):
	dp[x] = (dp[x - 1] + dp[x - k]) % 1000000007
for x in range(2, 100001):
	dp[x] = (dp[x] + dp[x - 1]) % 1000000007
for x in range(t):
	(a, b) = map(int, input().split())
	print(dp[b] - dp[a - 1] if dp[b] >= dp[a - 1] else dp[b] - dp[a - 1] + 1000000007)


def func(k, b):
	r = 1000000007
	if k == 1:
		mem = [2]
	else:
		mem = [1]
	y = [mem[0]]
	p = y[0]
	for j in range(1, b):
		s = mem[j - 1]
		if j > k - 1:
			s += mem[j - k]
		elif j == k - 1:
			s += 1
		s %= r
		mem.append(s)
		p += s
		y.append(p % r)
	return y
(t, k) = map(int, input().split())
y = func(k, 100002)
r = 1000000007
for test in range(t):
	(a, b) = map(int, input().split())
	if a == 1:
		print(y[b - 1] % r)
	else:
		print((y[b - 1] - y[a - 2]) % r)


def abhi(n):
	if n == 0:
		return 1
	elif dp[n] != -1:
		return dp[n]
	else:
		u = abhi(n - 1)
		if n >= w:
			u += abhi(n - w) % (1000000000 + 7)
		dp[n] = u
		return dp[n]
(t, w) = map(int, input().split())
dp = [-1] * 100001
pre = [0] * 100001
for i in range(1, 100001):
	pre[i] = (pre[i - 1] + abhi(i)) % (1000000000 + 7)
for j in range(t):
	(a, b) = map(int, input().split())
	print((pre[b] - pre[a - 1]) % (1000000000 + 7))


(t, k) = map(int, input().split())
d = [i for i in range(1, k + 1)]
for i in range(k, 100001):
	d.append((d[i - 1] + d[i - k] + 1) % 1000000007)
for i in range(t):
	(a, b) = map(int, input().split())
	print((d[b] - d[a - 1]) % 1000000007)


(t, k) = tuple(map(int, input().split()))
tests = []
m = 0
for i in range(t):
	(a, b) = tuple(map(int, input().split()))
	if b > m:
		m = b
	tests.append((a, b))
byvalue = [0] * (m + 1)
for i in range(k):
	byvalue[i] = 1

def f(n):
	if byvalue[n] != 0:
		return byvalue[n]
	else:
		res = (f(n - k) + f(n - 1)) % (10 ** 9 + 7)
		byvalue[n] = res
		return res
partialsums = [0]
for i in range(m + 1):
	partialsums.append((partialsums[-1] + f(i)) % (10 ** 9 + 7))
for i in range(t):
	print((partialsums[tests[i][1] + 1] - partialsums[tests[i][0]]) % (10 ** 9 + 7))


inp = input()
inp = inp.split()
k = int(inp[1])
t = int(inp[0])
maximumAsk = 0
cases = []
for _ in range(t):
	case = input()
	cc = []
	case = [int(i) for i in case.split()]
	a = case[0]
	b = case[1]
	cc.append(a)
	cc.append(b)
	if a > maximumAsk:
		maximumAsk = a
	if b > maximumAsk:
		maximumAsk = b
	cases.append(cc)
answers = [-1] * (maximumAsk + 1)

def getWays(n, k, M):
	M[0] = 1
	for i in range(1, n + 1):
		if i - k >= 0:
			M[i] = (M[i - 1] + M[i - k]) % 1000000007
		else:
			M[i] = M[i - 1] % 1000000007
getWays(maximumAsk, k, answers)
cumlative = [0] * (maximumAsk + 1)
for i in range(1, maximumAsk + 1):
	cumlative[i] = cumlative[i - 1]
	cumlative[i] += answers[i]
for case in cases:
	ret = 0
	start = case[0]
	end = case[1]
	ret = (cumlative[end] - cumlative[start - 1]) % 1000000007
	print(ret)


from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(10 ** 4)
M = 10 ** 9 + 7

def fn(l):
	if l in dp:
		return dp[l]
	if l < 0:
		return 0
	if l == 0:
		return 1
	dp[l] = (fn(l - 1) + fn(l - k)) % M
	return dp[l]
(q, k) = list(map(int, stdin.readline().split()))
dp = {}
lim = 10 ** 5 + 5
ps = [0] * lim
for i in range(lim):
	if i == 0:
		ps[i] = fn(i)
	else:
		ps[i] = (ps[i - 1] + fn(i)) % M
for _ in range(1):
	for _ in range(q):
		(a, b) = list(map(int, stdin.readline().split()))
		ans = (ps[b] - (ps[a - 1] if a >= 1 else 0) + M) % M
		print(ans)


import sys
from types import GeneratorType

def bootstrap(func, stack=[]):

	def wrapped_function(*args, **kwargs):
		if stack:
			return func(*args, **kwargs)
		else:
			call = func(*args, **kwargs)
			while True:
				if type(call) is GeneratorType:
					stack.append(call)
					call = next(call)
				else:
					stack.pop()
					if not stack:
						break
					call = stack[-1].send(call)
			return call
	return wrapped_function
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

@bootstrap
def solve(a):
	if a < 0:
		yield 0
	if dp[a] != -1:
		yield dp[a]
	dp[a] = (yield solve(a - 1)) + (yield solve(a - k))
	dp[a] = dp[a] % MOD
	yield dp[a]
(_, k) = Ri()
dp = [-1 for i in range(10 ** 5 + 1)]
dp[0] = 1
solve(10 ** 5)
for i in range(1, 10 ** 5 + 1):
	dp[i] += dp[i - 1]
for qq in range(_):
	(a, b) = Ri()
	print((dp[b] - dp[a - 1]) % MOD)


def main():
	from sys import stdin, stdout
	MOD = int(1000000000.0) + 7
	(T, k) = map(int, stdin.readline().split())
	fib = [x for x in range(1, k + 1)]
	for i in range(k, 100001):
		fib.append((fib[i - 1] + fib[i - k] + 1) % MOD)
	for _ in range(T):
		(a, b) = map(int, stdin.readline().split())
		stdout.write(str((fib[b] - fib[a - 1]) % MOD) + '\n')
main()


(t, k) = map(int, input().split())
l = []
m = 0
for i in range(t):
	(a, b) = map(int, input().split())
	m = max(m, b)
	l.append((a, b))
a = [0] * (m + 1)
for i in range(k):
	a[i] = 1
for i in range(k, m + 1):
	a[i] = a[i - 1] + a[i - k]
	a[i] %= 10 ** 9 + 7
s = [0] * (m + 1)
for i in range(1, m + 1):
	s[i] = s[i - 1] + a[i]
	s[i] %= 10 ** 9 + 7
for i in l:
	print(s[i[1]] - s[i[0] - 1] if s[i[1]] - s[i[0] - 1] >= 0 else s[i[1]] - s[i[0] - 1] + 10 ** 9 + 7)


a = [0] * 100001
b = [0] * 100002
(t, k) = map(int, input().split())
a[0] = 1
for i in range(1, 100001):
	a[i] = a[i - 1]
	if i >= k:
		a[i] += a[i - k]
	a[i] %= 10 ** 9 + 7
	b[i] = (b[i - 1] + a[i]) % (10 ** 9 + 7)
for i in range(t):
	(l, r) = map(int, input().split())
	print((b[r] - b[l - 1]) % (10 ** 9 + 7))


from sys import stdout
from sys import stdin

def get():
	return stdin.readline().strip()

def getf():
	return [int(i) for i in get().split()]

def put(a, end='\n'):
	stdout.write(str(a) + end)

def putf(a, sep=' ', end='\n'):
	stdout.write(sep.join([str(i) for i in a]) + end)
from collections import defaultdict as dd
d = dd(set)

def rec(s, cur, lmt, k):
	if cur + k <= lmt:
		rec(s + 'W' * k, cur + k, lmt, k)
	if cur + 1 <= lmt:
		rec(s + 'R', cur + 1, lmt, k)
	if cur == lmt:
		global d
		d[lmt].add(s)

def bruh():
	(t, k) = getf()
	lmt = 10 ** 5 + 1
	fn = [1] * lmt
	fn[k] = 2
	for i in range(k + 1, lmt):
		fn[i] = (fn[i - 1] + fn[i - 0 - k]) % (10 ** 9 + 7)
	rs = [0] * lmt
	rs[0] = fn[0]
	for i in range(1, lmt):
		rs[i] = (rs[i - 1] + fn[i]) % (10 ** 9 + 7)
	for i in range(t):
		(a, b) = getf()
		r = rs[b] - rs[a - 1]
		if r < 0:
			r += 10 ** 9 + 7
		put(r)
bruh()


mod = 7 + 10 ** 9
(t, k) = map(int, input().split())
x = [1] * 100001
for i in range(k, 100001):
	x[i] = (x[i - 1] + x[i - k]) % mod
for i in range(1, 100001):
	x[i] = (x[i] + x[i - 1]) % mod
for i in range(t):
	(a, b) = map(int, input().split())
	print((x[b] - x[a - 1]) % mod)


(num1, num2) = input().split()
t = int(num1)
k = int(num2)
abNum = []
for _ in range(t):
	(num1, num2) = input().split()
	abNum.append([int(num1), int(num2)])
nMaxFlw = 100001
lNum = 10 ** 9 + 7
nWays = [0] * nMaxFlw
nWays[0] = 1
for i in range(1, nMaxFlw):
	nWays[i] = nWays[i - 1]
	if i >= k:
		nWays[i] += nWays[i - k]
		nWays[i] %= lNum
for i in range(1, nMaxFlw):
	nWays[i] += nWays[i - 1]
	nWays[i] %= lNum
for i in range(t):
	print((nWays[abNum[i][1]] - nWays[abNum[i][0] - 1] + lNum) % lNum)


from sys import *
MAXN = 10 ** 5 + 228
MOD = 10 ** 9 + 7
(t, k) = (int(z) for z in stdin.readline().split())
dp = [0] * MAXN
dp[0] = 1
for i in range(1, MAXN):
	if i >= k:
		dp[i] = dp[i - k] + dp[i - 1]
	else:
		dp[i] = dp[i - 1]
	dp[i] %= MOD
for i in range(1, MAXN):
	dp[i] += dp[i - 1]
	dp[i] %= MOD
for i in range(t):
	(a, b) = (int(z) for z in stdin.readline().split())
	ans = (dp[b] - dp[a - 1] + MOD) % MOD
	stdout.write(str(ans) + '\n')


(t, k) = map(int, input().split())
m = 0
a = [0] * t
b = [0] * t
for i in range(t):
	(a[i], b[i]) = map(int, input().split())
	m = max(m, b[i])
z = [1] * k + [0] * (m - k + 1)
for i in range(k, m + 1):
	z[i] = (z[i - 1] + z[i - k]) % 1000000007
for i in range(1, m + 1):
	z[i] = (z[i] + z[i - 1]) % 1000000007
for i in range(t):
	print((z[b[i]] - z[a[i] - 1]) % 1000000007)


import random, math, sys
from copy import deepcopy as dc
from bisect import bisect_left, bisect_right
from collections import Counter
input = sys.stdin.readline
MOD = 10 ** 9 + 7

def solution(b, k):
	dp = [1] * (b + 1)
	for i in range(k, b + 1):
		dp[i] = (dp[i - k] % MOD + dp[i - 1] % MOD) % MOD
	for i in range(1, b + 1):
		dp[i] = (dp[i] % MOD + dp[i - 1] % MOD) % MOD
	return dp

def input_test():
	(t, k) = map(int, input().strip().split(' '))
	val = []
	maxi = 0
	for _ in range(t):
		(a, b) = map(int, input().strip().split(' '))
		val.append([a, b])
		maxi = max(maxi, b)
	dp = solution(maxi, k)
	for i in val:
		(a, b) = (i[0], i[1])
		print((dp[b] - dp[a - 1] + MOD) % MOD)

def test():
	pass
input_test()


_MODER = 10 ** 9 + 7
(t, k) = map(int, input().split())
abs = []
(min_a, max_b) = (float('inf'), -float('inf'))
for _ in range(t):
	(a, b) = map(int, input().split())
	min_a = min(min_a, a)
	max_b = max(max_b, b)
	abs.append((a, b))
t = [0] * (max_b + 1)
s = [0] * (max_b + 1)
for i in range(k):
	t[i] = 1
for i in range(k, max_b + 1):
	t[i] = (t[i - 1] + t[i - k]) % _MODER
for i in range(min_a, max_b + 1):
	s[i] = (s[i - 1] + t[i]) % _MODER
for (a, b) in abs:
	r = s[b] - s[a - 1]
	print(r if r >= 0 else _MODER + r)


(nb_cases, k) = [int(x) for x in input().split()]
reponse = []
dp = [0] * 100001
sum = [0] * 100001
if k == 1:
	dp[1] = 2
else:
	dp[1] = 1
sum[1] = dp[1]
for x in range(2, 100001):
	if k > x:
		dp[x] = 1
	elif k == x:
		dp[x] = 2
	else:
		dp[x] = (dp[x - 1] + dp[x - k]) % 1000000007
	sum[x] = (sum[x - 1] + dp[x]) % 1000000007
while nb_cases > 0:
	nb_cases -= 1
	(a, b) = [int(x) for x in input().split()]
	reponse.append((sum[b] - sum[a - 1]) % 1000000007)
for x in reponse:
	print(x)


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
int1 = lambda x: int(x) - 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))
ilelec = lambda : map(int1, input().split())
alelec = lambda : list(map(int1, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
(t, k) = ilele()
dp = [0] * 100001
for i in range(1, 100001):
	dp[i] += dp[i - 1] + 1
	if i - k >= 0:
		dp[i] += dp[i - k] + 1
	dp[i] %= MOD
for i in range(t):
	(a, b) = ilele()
	print((dp[b] - dp[a - 1]) % MOD)


dp = [-1 for i in range(100001)]
(t, k) = map(int, input().split())
m = 10 ** 9 + 7

def fl(n, k, m=10 ** 9 + 7):
	global dp
	if n == 0:
		return 1
	if dp[n] != -1:
		return dp[n]
	ans = 0
	if n >= k:
		ans = (ans + fl(n - k, k) % m) % m
	ans = (ans + fl(n - 1, k)) % m
	dp[n] = ans
	return ans % m
pre = [0 for i in range(100001)]
for i in range(100001):
	pre[i] = (pre[i - 1] + fl(i, k)) % m
for _ in range(t):
	(l, r) = map(int, input().split())
	print((pre[r] - pre[l - 1] + m) % m)


import sys
import math
import heapq
import bisect
from collections import Counter
from collections import defaultdict
from io import BytesIO, IOBase
import string

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None
		self.BUFSIZE = 8192

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
	return int(input())

def get_ints():
	return list(map(int, input().split(' ')))

def get_int_grid(n):
	return [get_ints() for _ in range(n)]

def get_str():
	return input().strip()

def get_strs():
	return get_str().split(' ')

def flat_list(arr):
	return [item for subarr in arr for item in subarr]

def yes_no(b):
	if b:
		return 'YES'
	else:
		return 'NO'

def binary_search(good, left, right, delta=1, right_true=False):
	limits = [left, right]
	while limits[1] - limits[0] > delta:
		if delta == 1:
			mid = sum(limits) // 2
		else:
			mid = sum(limits) / 2
		if good(mid):
			limits[int(right_true)] = mid
		else:
			limits[int(~right_true)] = mid
	if good(limits[int(right_true)]):
		return limits[int(right_true)]
	else:
		return False

def prefix_sums(a):
	p = [0]
	for x in a:
		p.append(p[-1] + x)
	return p

def solve_a():
	a = 'qwertyuiopasdfghjkl;zxcvbnm,./'
	c = get_str()
	s = get_str()
	if c == 'L':
		m = +1
	else:
		m = -1
	ans = ''.join([a[a.index(char) + m] for char in s])
	return ans

def solve_b():
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	m = int(input())
	queries = [int(x) for x in input().split(' ')]
	a_p = [a[0]]
	for i in range(1, n):
		a_p.append(a_p[-1] + a[i])
	for q in queries:
		l = -1
		r = n - 1
		while r - l > 1:
			m = (l + r) // 2
			if a_p[m] < q:
				l = m
			else:
				r = m
		return r + 1

def solve_c():
	(t, k) = get_ints()
	M = 10 ** 9 + 7
	n = 10 ** 5
	ways = [0] * (n + 1)
	p_ways = [0] * (n + 1)
	ways[0] = 1
	p_ways[0] = 1
	for i in range(1, n + 1):
		ways[i] += ways[i - 1]
		ways[i] %= M
		if i >= k:
			ways[i] += ways[i - k]
			ways[i] %= M
		p_ways[i] = (p_ways[i - 1] + ways[i]) % M
	ans = []
	for _ in range(t):
		(a, b) = get_ints()
		ans.append((p_ways[b] - p_ways[a - 1]) % M)
	return ans
print(*solve_c())


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
(t, k) = map(int, input().split())
l = [1]
mod = pow(10, 9) + 7
z = [0]
for i in range(1, 100002):
	if i < k:
		l.append(1)
	else:
		l.append(l[i - 1] + l[i - k])
	l[-1] = l[-1] % mod
	z.append((z[-1] + l[-1]) % mod)
for i in range(t):
	(a, b) = map(int, input().split())
	print((z[b] - z[a - 1]) % mod)


(n, k) = map(int, input().strip().split())
mod = 10 ** 9 + 7
hashmap = [1 for a in range(0, k)]
for a in range(k, 100000 + 1):
	hashmap.append(hashmap[a - k] % mod + hashmap[a - 1] % mod)
for d in range(1, len(hashmap)):
	hashmap[d] += hashmap[d - 1]
for a in range(0, n):
	(i, j) = map(int, input().strip().split())
	print((hashmap[j] - hashmap[i - 1]) % mod)