说明

在实验室信息技术部的修理过程中，工人们需要更换走廊中受损的地板砖，走廊的尺寸是 $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$ 取模。

2 0

7

3 0

22

3 1
2 1

8

提示

图 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。