问题描述

Anti Real Corporation 公司是一个致力于用略微不同的方式丰富日常生活的组织。

Anti Real Corporation 公司的插座有一种稍微不同形状的插孔。插座呈纵向排列，有 $H$ 行、横向排列有 $W$ 列的孔。插头可以在未使用的孔中选择使用上下或左右连续的 $2$ 个位置。换句话说，假设我们将从上到下编号为第 $i$ 行、从右到左编号为第 $j$ 列的孔称为 ($i$,$j$)。

• 可以选择使用 ($i$,$j$) 和 ($i+1$,$j$) ($1 ≦ i ≦ H-1$, $1 ≦ j ≦ W$) 这两个孔。
• 可以选择使用 ($i$,$j$) 和 ($i$,$j+1$) ($1 ≦ i ≦ H$, $1 ≦ j ≦ W-1$) 这两个孔。

在插入插头时，不能多个插头同时共享同一个孔，也不能使用带有插头盖（后述）的孔。

某天，公司的总经理决定在 $N$ 天内，在每个工作日的营业开始时执行以下两种操作之一，以增加插头插入的乐趣。

• 选择一个未使用的孔，插入插头盖。
• 选择一个插入了插头盖的孔，将插头盖拿掉，变回未使用状态。

初始时，所有的孔都是未使用的。

总经理指示部长记录每个工作日的操作方式，包括有多少种插入插座的方法，并在最后一天报告结果。组合中，插头之间和插头盖之间没有区别，并且将不使用插头的情况视为一种方法。

然而，直到截止日期前，部长都忘记了这件事，但他在意外中找到了插头盖的历史记录，并决定以某种方式得出每一天的结果。

因为研究所有可能的组合看起来不太可能，所以开发团队找到了你，希望你能编写一个程序来解决这个问题。

输入

输入从标准输入中按以下格式给出。

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

• 第 $1$ 行包含两个整数 $H (1 ≦ H ≦ 2)$ 和 $W (1 ≦ W ≦ 10^{11})$，用空格分隔。描述了插座的形状，其中插座是纵向 $H$ 行、横向 $W$ 列的孔。
• 第 $2$ 行包含一个整数 $N (1 ≦ N ≦ 20,000)$，表示操作的日程安排。
• 第 $3$ 行到第 $N$ 行给出了操作的信息。其中第 $i$ 行包含了两个整数 $S_i (1 ≦ S_i ≦ H)$ 和 $T_i (1 ≦ T_i ≦ W)$，表示第 $i$ 天的操作。如果 ($S_i$, $T_i$) 在当天的营业开始之前是未使用的，则表示在当天的营业开始时插入插头盖；否则表示拿掉插头盖恢复为未使用状态。

部分分

本问题设有部分分。

• 如果满足 $W ≦ 5,000 , N ≦ 3,000$ 的数据集 $1$ 的正确解答，将得到 $10$ 分。
• 如果满足 $W ≦ 100,000 , N ≦ 3,000$ 的数据集 $2$ 的正确解答，除了之前的分数外还能得到额外的 $30$ 分。
• 如果满足额外条件的数据集 $3$ 的正确解答，除了之前的分数外还能得到额外的 $60$ 分。

输出

请输出 $N$ 行。其中第 $i$ 行输出在第 $i$ 天的营业开始时的操作后，可能的插座布局总数除以 $1000000007 (= 1,000,000,007)$ 的余数。

输入示例1

2 3
3
1 1
2 3
1 1

输出示例1

10
5
10

第 $1$ 天操作后，插座布局如下图所示。图中用六边形表示有插头盖的位置。

因此，共有 $10$ 种可能的布局。

输入示例2

2 4
5
1 2
1 1
2 2
2 1
1 4

输出示例2

27
17
7
7
3