P15529 [ROIR 2015 Day 2] tiling 铺砖

在实验室信息技术部的修理过程中，工人们需要更换走廊中受损的地板砖，走廊的尺寸是 $2 \times n$ 米。工人们有无限供应的两种尺寸的砖：$1 \times 2$ 米和 $1 \times 1$ 米砖。此外，$1 \times 2$ 米的砖可以旋转 $90$ 度使用，可以沿走廊方向或垂直放置。 工人们已经开始修理，并在某些地方铺设了 $k$ 块 $1 \times 1$ 米的砖。为了完成修理，项目经理需要准备后续工作的计划。他想知道，有多少种方法可以铺设剩余的位置。这个数字需要模 $10^9 + 7$ 计算。 **任务**：编写一个程序，给定走廊的长度 $n$ 和已铺设的砖的位置，确定剩余砖铺设的方式数，并输出结果。

输入文件的第一行包含两个整数：$n$ —— 走廊的长度，$k$ —— 已铺设 $1 \times 1$ 砖的数量（$1 \leq n \leq 100,000$，$0 \leq k < 2n$）。接下来的 $k$ 行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 块砖铺设在走廊的第 $x_i$ 米，第 $y_i$ 行（$1 \leq x_i \leq n$，$1 \leq y_i \leq 2$）。

输出文件应该包含一个整数 —— 走廊剩余砖铺设的方式数，结果对 $10^9 + 7$ 取模。

 图 1. 第一个例子中的所有瓷砖安装方法。  图 2. 第三个例子中所有的瓷砖安装方法。 已铺设的瓷砖用灰色标记。 ### 评分系统与子任务描述 #### 子任务 1（20 分） * $1 \leq n \leq 8$，$k = 0$ * 若所有测试都通过，才能得分。 #### 子任务 2（20 分） * $1 \leq n \leq 1000$，$k = 0$ * 若所有测试都通过，才能得分。 #### 子任务 3（20 分） * $1 \leq n \leq 100,000$，$k = 0$ * 若所有测试都通过，才能得分。 #### 子任务 4（40 分） * $1 \leq n \leq 100,000$，$1 \leq k \leq 2n$ * 该子任务有 $20$ 个测试，每个测试得分为 $2$ 分，每个测试独立评分。 翻译来源：GPT 5.2。