Teaching Mastery

Limits: 4 sec., 256 MiB

This statement was translated automatically from Ukrainian.

While studying at Ivan Franko National University of Lviv, Zenyk was always impressed by the skill and professionalism of the professors. He often thought that he would definitely become a teacher in the future, because teaching is so incredibly interesting. Zenyk tried very hard to achieve his goal, but due to the complexity of the profession, he was not given the opportunity to teach students. Of course, Zenyk is a very determined person and does not give up his dreams, so he finally achieved the opportunity to teach at his favorite university, except that he now lays tiles (in Ukrainian, the words for "to teach" and "to lay [tiles]" share the same root).

Zenyk has to lay 2 more rows of tiles, with \(n\) cells each. Each row has a height of one cell. He has tiles of size \(1 \times 1\) and \(1 \times 2\). He must lay them row by row, but he can rotate them by 90 degrees, meaning he can rotate a \(1 \times 2\) tile to get a \(2 \times 1\) tile.

Zenyk is very interested in the following question: in how many ways can he finish laying the tiles if in the first row he has already filled the first \(a\) cells, and in the second — the first \(b\). He has \(q\) such questions. Help him answer them. Since the answer can be very large, print it modulo \(10^9 + 7\).

Input

The first line contains two integers \(n\) and \(q\) — the width of the rows for tiles and the number of queries, respectively.

The next \(q\) lines each contain two integers \(a_i\) and \(b_i\) — the number of filled cells in the first and second rows, respectively.

Output

In \(q\) lines, output one integer each — the number of ways to completely fill the two rows modulo \(10^9 + 7\).

Constraints

\(1 \le n, q \le 10^5\),

\(0 \le a_i, b_i \le n\).

Problem evaluation consists of the following subtasks:

1 point — example from the statement,

5 points — a block of tests in which \(a_i = n\),

5 points — a block of tests in which \(a_i = b_i\),

5 points — a block of tests in which \(q = 1\),

9 points — a block of tests in which \(1 \le n, q \le 10^5\) and \(0 \le a_i, b_i \le n\).

Points for a subtask will be awarded only if you give the correct answer to all tests in the subtask.

Samples

Input (stdin) сopy	Output (stdout) сopy
5 2 3 3 3 4	7 3

Notes

In the case where \(a_i = b_i = n\), Zenyk does not need to place any tiles, and therefore there is one way to completely fill the two rows — placing no tiles at all.