Рекурсия или ДП? - Pascal - Ответ 8504565

Задача 7. Укладка плитки
Имя входного файла:
tiling.in
Имя выходного файла:
tiling.out
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
В процессе ремонта в Лаборатории Информационных Технологий строителям необходимо заменить поврежденные напольные плитки в коридоре лаборатории, который имеет размер 2×n метров. В распоряжении строителей есть неограниченный запас плиток двух размеров: 1×2 метра и 1×1 метр. При этом плитки размером 1×2 метра перед укладкой разрешается поворачивать на 90 градусов и размещать как вдоль, так и поперек коридора.
Строители уже начали ремонт и уложили в некоторых местах пола коридора k плиток размером 1×1. Для завершения ремонта прорабу необходимо подготовить план дальнейших работ. Для этого ему надо решить, каким образом уложить плитки на места, где они еще не уложены. Это можно сделать различными способами и прораб хочет перебрать все варианты и выбрать самый удачный. Перед тем как это сделать, прораб хочет знать, какое количество вариантов ему придется рассмотреть. Это число требуется найти по модулю 10⁹+7.
Требуется написать программу, которая по заданной длине коридора n и расположению плиток, которые уже уложены, определяет количество способов укладки плиток на оставшиеся места. Ответ необходимо вывести по модулю 10⁹+7.
Формат входного файла
Первая строка входного файла содержит два целых числа: n—длину коридора и
k—количество уже уложенных единичных плиток (1≤n≤100000, 0≤k<2n).
Последующие k строк содержат по два целых числа xi и yi, которые задают позиции уже уложенных единичных плиток, i-я плитка уложена на xi-м метре коридора в yi-м ряду (1≤xi≤n, 1≤yi≤2).
Формат выходного файла
Выходной файл должен содержать одно целое число — количество способов укладки плиток в коридоре, взятое по модулю 10⁹+7.
римеры входных и выходных файлов

tiling.in	tiling.out
2 0	7
3 0	22
3 1	8