Викладацька майстерність

Limits: 4 sec., 256 MiB

Під час навчання у Львівському національному університеті імені Івана Франка Зеника завжди вражала майстерність і професіоналізм викладачів. Він часто думав що неодмінно стане викладачем у майбутньому, адже викладати це ж неймовірно цікаво. Зеник дуже старався, щоб досягнути своєї мети, але через всю складність професії йому не дали можливості вчити студентів. Звісно Зеник дуже цілеспрямована людина і не полишає своїх мрій, тому він все ж добився можливості викладати в улюбленому виші, щоправда викладає він плитку.

Зенику залишилося викласти ще 2 ряди плиточок, по \(n\) клітинок кожен. Кожен ряд має висоту в одну клітинку. В нього є плитки розміру \(1 \times 1\) та \(1 \times 2\). Він повинен викладати їх по рядах, але може повертати на 90 градусів, тобто він може повернути плитку розміру \(1 \times 2\) і отримати плитку \(2 \times 1\).

Зеника дуже цікавить таке питання: скількома способами можна довикладати плитку, якщо в першому ряді він вже заповнив перші \(a\) клітинок, а в другому — перші \(b\). В нього є \(q\) таких запитань. Допоможіть йому відповісти на них. Оскільки відповідь може бути дуже великою, виведіть її по модулю \(10^9 + 7\).

Input

У першому рядку задано два цілі числа \(n\) та \(q\) — ширина рядів для плиточок та кількість запитів відповідно.

У наступних \(q\) рядках задано по два цілі числа \(a_i\) та \(b_i\) — кількість заповнених клітинок в першому та другому рядах відповідно.

Output

В \(q\) рядках виведіть по одному цілому числу — кількість способів заповнити повністю два ряди по модулю \(10^9 + 7\).

Constraints

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

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

Оцінювання задачі складається із наступних блоків:

1 бал — приклад з умови,

5 балів — блок тестів у яких \(a_i = n\),

5 балів — блок тестів у яких \(a_i = b_i\),

5 балів — блок тестів у яких \(q = 1\),

9 балів — блок тестів у яких \(1 \le n, q \le 10^5\) та \(0 \le a_i, b_i \le n\).

Бали за блок ви отримаєте лише якщо дасте правильну відповідь на всі тести з блоку.

Samples

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

Notes

У випадку \(a_i = b_i = n\) Зенику не потрібно ставити плиточки, а отже в нього один спосіб заповнити повністю два ряди — не ставити жодну плитку.