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).

Difficulty: interview

Starter code:

Solutions:
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 = list(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 = list(map(int, input().split(' ')))
    print((sums[b+1]-sums[a])%(10**9+7))


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)


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)

t, k = list(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 = list(map(int, input().split()))
    result = (s[b] - s[a-1] + mod) % mod
    print(result)


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)

import sys

def solve():
    MOD = 1000000007
    size = 100003
    t, groupsize = read()
    mem = [0]*size
    summ = [0]*size
    for i in range(len(mem)):
        mem[i] = ((mem[i - 1] + mem[i - groupsize] if i >= groupsize else mem[i-1]) % MOD) if i > 0 else 1
    for i in range(len(summ)):
        summ[i] = (mem[i] + summ[i - 1])%MOD if i > 0 else mem[i]
    for i in range(t):
        a, b = read()
        print((summ[b]-summ[a-1]+MOD)%MOD)
    
def read(mode=2):
    inputs = input().strip()
    if mode == 0: return inputs  # String
    if mode == 1: return inputs.split()  # List of strings
    if mode == 2: return list(map(int, inputs.split()))  # List of integers
def write(s="\n"):
    if s is None: s = ""
    if isinstance(s, list): s = " ".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 sys
def solve():
    MOD = 1000000007
    size = 100003
    t, groupsize = read()
    mem = [0]*size
    summ = [0]*size
    for i in range(len(mem)):
        mem[i] = ((mem[i - 1] + mem[i - groupsize] if i >= groupsize else mem[i-1]) % MOD) if i > 0 else 1
    for i in range(len(summ)):
        summ[i] = (mem[i] + summ[i - 1]) % MOD if i > 0 else mem[i]
    res = list()
    for i in range(t):
        a, b = read()
        res.append((summ[b]-summ[a-1]+MOD)%MOD)
        # print((summ[b]-summ[a-1]+MOD)%MOD)
    return res

def read(mode=2):
    inputs = input().strip()
    if mode == 0: return inputs  # String
    if mode == 1: return inputs.split()  # List of strings
    if mode == 2: return list(map(int, inputs.split()))  # List of integers
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 sys
def solve():
    MOD = 1000000007
    size = 100003
    t, groupsize = read()
    mem = [0]*size
    summ = [0]*size
    for i in range(len(mem)):
        mem[i] = ((mem[i - 1] + mem[i - groupsize] if i >= groupsize else mem[i-1]) % MOD) if i > 0 else 1
    for i in range(len(summ)):
        summ[i] = (mem[i] + summ[i - 1]) % MOD if i > 0 else mem[i]
    res = list()
    for i in range(t):
        a, b = read()
        res.append((summ[b]-summ[a-1]+MOD)%MOD)
        # print((summ[b]-summ[a-1]+MOD)%MOD)
    return res

def read(mode=2):
    inputs = input().strip()
    if mode == 0: return inputs  # String
    if mode == 1: return inputs.split()  # List of strings
    if mode == 2: return list(map(int, inputs.split()))  # List of integers
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 sys
def solve():
    MOD = 1000000007
    size = 100003
    t, groupsize = read()
    mem = [0]*size
    summ = [0]*size
    mem[0] = 1
    for i in range(1, len(mem)):
        mem[i] = (mem[i - 1] + mem[i - groupsize] if i >= groupsize else mem[i-1]) % 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  # String
    if mode == 1: return inputs.split()  # List of strings
    if mode == 2: return list(map(int, inputs.split()))  # List of integers
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 sys
def solve():
    MOD = 1000000007
    size = 100003
    t, groupsize = read()
    mem = [0]*size
    summ = [0]*size
    mem[0] = 1
    for i in range(1, len(mem)):
        mem[i] = (mem[i - 1] + mem[i - groupsize] if i >= groupsize else mem[i-1]) % 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  # String
    if mode == 1: return inputs.split()  # List of strings
    if mode == 2: return list(map(int, inputs.split()))  # List of integers
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 sys
def solve():
    MOD = 1000000007
    size = 100003
    t, groupsize = read()
    mem = [0]*size
    summ = [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  # String
    if mode == 1: return inputs.split()  # List of strings
    if mode == 2: return list(map(int, inputs.split()))  # List of integers
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 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  # String
    if mode == 1: return inputs.split()  # List of strings
    if mode == 2: return list(map(int, inputs.split()))  # List of integers
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 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  # String
    if mode == 1: return inputs.split()  # List of strings
    if mode == 2: return list(map(int, inputs.split()))  # List of integers
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 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  # String
    if mode == 1: return inputs.split()  # List of strings
    if mode == 2: return list(map(int, inputs.split()))  # List of integers
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 sys
import array
import io


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()
    output = io.StringIO()
    for i in range(t):
        a, b = read()
        strtemp = str((summ[b]-summ[a-1]+MOD)%MOD)
        output.write(strtemp+'\n')
        # res.append((summ[b]-summ[a-1]+MOD)%MOD)
    print(output.getvalue())

def read(mode=2):
    inputs = input().strip()
    if mode == 0: return inputs  # String
    if mode == 1: return inputs.split()  # List of strings
    if mode == 2: return list(map(int, inputs.split()))  # List of integers
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 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)


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 i in range(t):
	a, b = (int(x) for x in sys.stdin.readline().split())
	print((l[b] - l[a - 1] + mod) % 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()

#a, b, c, d = [int(x) for x in stdin.readline().split()]
#a, b, c, d = map( int, stdin.readline().split() )
from sys import stdin, stdout
modconst=1000000007

n,k=list(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=list(map(int, stdin.readline().split()))
    stdout.write( str( (ss[b]-ss[a-1]+modconst )%modconst ) + "\n" )


#a, b, c, d = [int(x) for x in stdin.readline().split()]
#a, b, c, d = map( int, stdin.readline().split() )
from sys import stdin, stdout
modconst=1000000007

n,k=list(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=list(map(int, stdin.readline().split()))
    stdout.write( str( (ss[b]-ss[a-1]+modconst )%modconst ) + "\n" )


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" )

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)