602. Flowers

0

Medium

Marmot enjoys eating flowers for dinner. He eats a combination of red and white flowers, but he has a rule: he can only eat white flowers in groups of size k. Marmot wants to know how many ways he can eat between a and b flowers. Since the number of ways can be large, the answer should be printed modulo 1000000007 (10

^{9}+ 7).Input Format

The input consists of multiple test cases.
The first line contains two integers t and k (1 ≤ t, k ≤ 105), where t represents the number of test cases.
The next t lines contain two integers ai and bi (1 ≤ ai ≤ bi ≤ 105), describing the i-th test case.

Output Format

Print t lines to the standard output. The i-th line should contain the number of ways in which Marmot can eat between ai and bi flowers at dinner modulo 1000000007 (10

^{9}+ 7).Example

Input

3 2
1 3
2 3
4 4

Output

6
5
5

Constraints

1 ≤ t, k ≤ 10

1 ≤ ai ≤ bi ≤ 10

^{5}1 ≤ ai ≤ bi ≤ 10

^{5}Loading...

View Submissions

Console