Викладацька майстерність
Обмеження: 4 сек., 256 МіБ
Під час навчання у Львівському національному університеті імені Івана Франка Зеника завжди вражала майстерність і професіоналізм викладачів. Він часто думав що неодмінно стане викладачем у майбутньому, адже викладати це ж неймовірно цікаво. Зеник дуже старався, щоб досягнути своєї мети, але через всю складність професії йому не дали можливості вчити студентів. Звісно Зеник дуже цілеспрямована людина і не полишає своїх мрій, тому він все ж добився можливості викладати в улюбленому виші, щоправда викладає він плитку.
Зенику залишилося викласти ще 2 ряди плиточок, по n клітинок кожен. Кожен ряд має висоту в одну клітинку. В нього є плитки розміру 1×1 та 1×2. Він повинен викладати їх по рядах, але може повертати на 90 градусів, тобто він може повернути плитку розміру 1×2 і отримати плитку 2×1.
Зеника дуже цікавить таке питання: скількома способами можна довикладати плитку, якщо в першому ряді він вже заповнив перші a клітинок, а в другому — перші b. В нього є q таких запитань. Допоможіть йому відповісти на них. Оскільки відповідь може бути дуже великою, виведіть її по модулю 109+7.
Вхідні дані
У першому рядку задано два цілі числа n та q — ширина рядів для плиточок та кількість запитів відповідно.
У наступних q рядках задано по два цілі числа ai та bi — кількість заповнених клітинок в першому та другому рядах відповідно.
Вихідні дані
В q рядках виведіть по одному цілому числу — кількість способів заповнити повністю два ряди по модулю 109+7.
Обмеження
1≤n,q≤105,
0≤ai,bi≤n.
Оцінювання задачі складається із наступних блоків:
1 бал — приклад з умови,
5 балів — блок тестів у яких ai=n,
5 балів — блок тестів у яких ai=bi,
5 балів — блок тестів у яких q=1,
9 балів — блок тестів у яких 1≤n,q≤105 та 0≤ai,bi≤n.
Бали за блок ви отримаєте лише якщо дасте правильну відповідь на всі тести з блоку.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
5 2 3 3 3 4 | 7 3 |
Примітки
У випадку ai=bi=n Зенику не потрібно ставити плиточки, а отже в нього один спосіб заповнити повністю два ряди — не ставити жодну плитку.