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 (109 + 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 (109 + 7).
Example
Input
3 2
1 3
2 3
4 4
Output
6
5
5
Constraints
1 ≤ t, k ≤ 105
1 ≤ ai ≤ bi ≤ 105
1 ≤ ai ≤ bi ≤ 105
Loading...
View Submissions
Console