Задача E. Укладка плитки

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:1 сек
Входной файл:tiling.in   Ограничение памяти:256 Мб
Выходной файл:tiling.out  

Условие

В процессе ремонта в Лаборатории Информационных Технологий строителям необходимо заменить поврежденные напольные плитки в коридоре лаборатории, который имеет размер 2 × n метров. В распоряжении строителей есть неограниченный запас плиток двух размеров: 1 × 2 метра и 1 × 1 метр. При этом плитки размером 1 × 2 метра перед укладкой разрешается поворачивать на 90 градусов и размещать как вдоль, так и поперек коридора.

Строители уже начали ремонт и уложили в некоторых местах пола коридора k плиток размером 1 × 1. Для завершения ремонта прорабу необходимо подготовить план дальнейших работ. Для этого ему надо решить, каким образом уложить плитки на места, где они еще не уложены. Это можно сделать различными способами и прораб хочет перебрать все варианты и выбрать самый удачный. Перед тем как это сделать, прораб хочет знать, какое количество вариантов ему придется рассмотреть. Это число требуется найти по модулю 109 + 7.

Требуется написать программу, которая по заданной длине коридора n и расположению плиток, которые уже уложены, определяет количество способов укладки плиток на оставшиеся места. Ответ необходимо вывести по модулю 109 + 7.

Пояснения к примерам

Внимание! Третий тест не подходит под ограничения для первых трех подзадач, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на все тесты из примера. Решение должно выводить правильный ответ на третий тест даже, если оно рассчитано на решение только каких-либо подзадач из первых трех.

Рисунок 1. Все способы укладки плиток в первом примере

Рисунок 2. Все способы укладки плиток в третьем примере. Уже уложенная плитка отмечена серым цветом.

Система оценивания и описание подзадач

Подзадача 1 (20 баллов)

1 ≤ n ≤ 8, k = 0

Баллы за подзадачу начисляются только в случае, если все тесты подзадачи пройдены.

Подзадача 2 (20 баллов)

1 ≤ n ≤ 1000, k = 0

Баллы за подзадачу начисляются только в случае, если все тесты подзадачи пройдены.

Подзадача 3 (20 баллов)

1 ≤ n ≤ 100 000, k = 0

Баллы за подзадачу начисляются только в случае, если все тесты подзадачи пройдены.

Подзадача 4 (40 баллов)

1 ≤ n ≤ 100 000, 1 ≤ k ≤ 2 n

В этой подзадаче 20 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Формат входного файла

Первая строка входного файла содержит два целых числа: n — длину коридора и k — количество уже уложенных единичных плиток.

Последующие k строк содержат по два целых числа xi и yi, которые задают позиции уже уложенных единичных плиток, i-я плитка уложена на xi-м метре коридора в yi-м ряду.

Формат выходного файла

Выходной файл должен содержать одно целое число — количество способов укладки плиток в коридоре, взятое по модулю 109 + 7.

Ограничения

1 ≤ n ≤ 100 000; 0 ≤ k ≤ 2 n; 1 ≤ xi ≤ n; 1 ≤ yi ≤ 2.

Примеры тестов

Входной файл (tiling.in) Выходной файл (tiling.out)
1
2 0
7
2
3 0
22
3
3 1
2 1
8

0.047s 0.007s 19