AT_arc025_4.[ARC025D] コンセント

Anti Real Corporation 公司致力于以一种独特的方法来丰富每个人的日常生活。

公司的插座插孔形状特殊，与众不同，由 $H$ 行 $W$ 列的小孔组成。插头可以占用相邻的两个未使用小孔，这两个小孔可以是上下邻接或左右邻接。具体来说，如果我们标记第 $i$ 行第 $j$ 列的小孔为 ($i$, $j$)，那么：

• 可以选择 ($i$, $j$) 和 ($i+1$, $j$) 的两个小孔（$1 \leq i \leq H-1$，$1 \leq j \leq W$）。
• 可以选择 ($i$, $j$) 和 ($i$, $j+1$) 的两个小孔（$1 \leq i \leq H$，$1 \leq j \leq W-1$）。

插头在插入时不能与已用的小孔或已经插上插孔盖的小孔重叠。

某一天，总裁为增加插头插入的趣味性，决定在接下来的 $N$ 天中，每天在营业开始时执行以下两个操作中的一个：

• 选中一个未使用的小孔，安装插孔盖。
• 选中一个已安装插孔盖的小孔，移除插孔盖，使其变为未使用状态。

初始状态下，所有的小孔都是未使用的。

总裁要求部门经理在这 $N$ 天中每天记录可能的插头组合方式数，并在最后一天报告结果。在考虑组合方式时，不区分不同的插头间以及不同的插孔盖间的差异，即使不使用任何插头也算作一种组合方式。

然而，经理直到截止时间前才想起来这件事。幸运的是，他发现了插孔盖的历史记录，通过这些记录尝试确定每一天可能的组合方式。

由于显然无法逐一检查所有组合，开发团队的你被委派编写一个程序，来有效地解决这个问题。

输入以以下格式从标准输入给出：

$H$ $W$ $N$ $S_1$ $T_1$ $S_2$ $T_2$ ... $S_N$ $T_N$

• 第一行包含两个整数 $H$ 和 $W$（$1 \leq H \leq 2$，$1 \leq W \leq 10^{11}$），描述插座的形状为 $H$ 行 $W$ 列。
• 第二行包含一个整数 $N$（$1 \leq N \leq 20,000$），表示操作的天数。
• 接下来的 $N$ 行中，每行包含两个整数 $S_i$ 和 $T_i$（$1 \leq S_i \leq H$，$1 \leq T_i \leq W$），表示在第 $i$ 天的操作：如果在当天营业开始前 ($S_i$, $T_i$) 是未使用状态，则安装插孔盖；否则，移除插孔盖。

输出 $N$ 行。第 $i$ 行输出在第 $i$ 天营业开始后的操作后，所有可能的插头组合总数对 $1000000007\ (=\ 1,000,000,007)$ 取模的结果。

部分得分

本题有部分得分设定。

• 对满足 $W \leq 5,000$ 且 $N \leq 3,000$ 的数据集 $1$，正确解答可得 $10$ 分。
• 对满足 $W \leq 100,000$ 且 $N \leq 3,000$ 的数据集 $2$，除了上述得分外，再得 $30$ 分。
• 对于无限制的数据集 $3$，除了上述得分外，额外得到 $60$ 分。

示例说明 1

在第 $1$ 天的操作后，插孔的状态如下图所示。图中六边形表示插孔盖的位置。共有以下 $10$ 种可能的配置。

本翻译由 AI 自动生成