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