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

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$ Зенику не потрібно ставити плиточки, а отже в нього один спосіб заповнити повністю два ряди — не ставити жодну плитку.