Problem Description
Ranald is eating flowers for lunch today. He has bought an infinite supply of red and white flowers.
Ranald eats flowers one by one, but he has decided that he must only eat white flowers in consecutive groups of K. There are no limitations on how and when he eats the red flowers.
There are D days he will be planning his lunches for. On each day i, he wants to eat between Ai and Bi flowers. Help him find out what is the number of possible lunches he can have for each day. Two ways are considered different if at some point in time, he eats one type of flower in one way and another type of flower in another. Since this number can be very large, output it modulo 109 + 7.
Limits
For all subtasks: 1 ≤ D ≤ 105.
Subtask 1 (17%): 1 ≤ K ≤ 18, 1 ≤ Ai ≤ Bi ≤ 18.
Subtask 2 (23%): K = 1, 1 ≤ Ai ≤ Bi ≤ 106.
Subtask 3 (24%): 1 ≤ K ≤ 106, 1 ≤ Ai = Bi ≤ 106.
Subtask 4 (36%): 1 ≤ K ≤ 106, 1 ≤ Ai ≤ Bi ≤ 106.
Subtask 5 (0%): Sample Testcases.
Input
The first line of input contains two integers, K and D.
The next D lines of input contains two integers each, Ai and Bi for each day.
Output
The output should contain D lines, with line i containing the number of possible lunches Ranald could have on day i, modulo 109 + 7.
Sample Testcase 1
Input
2 3
1 3
2 3
4 4
Output
6
5
5
Explanation
For K = 2, Rar can eat "R", "RR", "WW", "RRR", "RWW", "WWR", "WWWW" or "RWWR".