Задача №112750. Укладка плитки
В процессе ремонта в Лаборатории Информационных Технологий строителям необходимо заменить поврежденные напольные плитки в коридоре лаборатории, который имеет размер 2 × \(n\) метров. В распоряжении строителей есть неограниченный запас плиток двух размеров:
1 × 2 метра и 1 × 1 метр. При этом плитки размером 1 × 2 метра перед укладкой разрешается поворачивать на 90 градусов и размещать как вдоль, так и поперек коридора.
Строители уже начали ремонт и уложили в некоторых местах пола коридора \(k\) плиток размером 1 × 1. Для завершения ремонта прорабу необходимо подготовить план дальнейших работ. Для этого ему надо решить, каким образом уложить плитки
на места, где они еще не уложены. Это можно сделать различными способами и прораб хочет перебрать все варианты и выбрать самый удачный. Перед тем как это сделать, прораб хочет знать, какое количество вариантов ему придется рассмотреть. Это
число требуется найти по модулю \(10^9\) + 7.
Требуется написать программу, которая по заданной длине коридора \(n\) и расположению плиток, которые уже уложены, определяет количество способов укладки плиток на оставшиеся места. Ответ
необходимо вывести по модулю \(10^9\) + 7.
Первая строка входного файла содержит два целых числа: \(n\) — длину коридора и \(k\) — количество уже уложенных единичных плиток (1 ≤ \(n\) ≤ 100 000, 0 ≤ \(k\) < 2\(n\)).
Последующие \(k\) строк содержат по два целых числа \(x_i\)
и \(y_i\) , которые задают позиции уже уложенных единичных плиток, \(i\)-я плитка уложена на \(x_i\)-м метре коридора в \(y_i\)-м ряду (1 ≤ \(x_i\) ≤ \(n\), 1 ≤ \(y_i\) ≤ 2)
Выходной файл должен содержать одно целое число — количество способов укладки плиток в коридоре, взятое по модулю \(10^9\) + 7.
Внимание! Третий тест не подходит под ограничения для первых трех подзадач, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на все тесты из примера. Решение должно выводить правильный ответ на третий тест даже, если оно рассчитано на решение только каких-либо подзадач из первых трех.
Все способы укладки плиток для первого примера:
Все способы укладки плиток для третьего примера (уже уложенная плитка отмечена серым цветом):
.gif )
Подзадача 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 балла. Баллы за каждый тест начисляются независимо
2 0
7
3 0
22
3 1 2 1
8