在实验室信息技术部的修理过程中，工人们需要更换走廊中受损的地板砖，走廊的尺寸是 米。工人们有无限供应的两种尺寸的砖： 米和 米砖。此外， 米的砖可以旋转 度使用，可以沿走廊方向或垂直放置。
工人们已经开始修理，并在某些地方铺设了 块 米的砖。为了完成修理，项目经理需要准备后续工作的计划。他想知道，有多少种方法可以铺设剩余的位置。这个数字需要模 计算。
任务：编写一个程序，给定走廊的长度 和已铺设的砖的位置，确定剩余砖铺设的方式数，并输出结果。
输入文件的第一行包含两个整数： —— 走廊的长度， —— 已铺设 砖的数量（，）。接下来的 行包含两个整数 和 ，表示第 块砖铺设在走廊的第 米，第 行（，）。
输出文件应该包含一个整数 —— 走廊剩余砖铺设的方式数，结果对 取模。
2 0
7
3 0
22
3 1 2 1
8
图 1. 第一个例子中的所有瓷砖安装方法。
图 2. 第三个例子中所有的瓷砖安装方法。
已铺设的瓷砖用灰色标记。
翻译来源：GPT 5.2。
