gayle-storm

We all know that Gayle likes dealing only in fours and sixes.Therefore the balls he faced can be represented as a sequence of fours and sixes.

But Gayle likes to hit sixes only in groups of size S (i.e. Once he starts hitting a six, he doesn't stop until he hits exactly S sixes). He may start hitting sixes immediately after ending a group of S sixes. This new group is considered different from previous one.

Abishek was told that Gayle played some number in range [a,b] (a & b included) number of balls. Being a fan of Gayle, Abishek know value of S. He now tries to determine how many ways Gayle would have scored through out his innings. 

Help Abishek in finding out what he requires. As the result can be very large print it modulo 1000000007.
INPUT :
First line contains number of test cases T.
Second line contains the size S.
The next T lines contains pairs of integers a and b.

OUTPUT :
Print T lines, answer for each test case in a new line.

CONSTRAINTS :
1 ≤ T ≤ 1000000
1 ≤ s ≤ 100000
1 ≤ a ≤ b ≤ 100000

Problem Setter : Abishek

SAMPLE INPUT
3
2
1 3
2 3
4 4

SAMPLE OUTPUT
6
5
5

Explanation

S = 2
Case #1 : a = 1, b = 3
Gayle would have played in any of these 6 ways, {4} {4,4} {6,6} {4,4,4} {4,6,6} {6,6,4}
Case #3 : a = 4, b = 4
Gayle faces exactly 4 balls. All possible cases would be {4,4,4,4} {4,4,6,6} {4,6,6,4} {6,6,4,4} {6,6,6,6}

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: