← 返回题目列表

AtCoder · arc025_4

D. 插座

中文机器翻译题面 查看原题

問題文

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

Anti Real Corporation 的出口形状有些不寻常。出水口是垂直的 H 线,水平 W 它具有排列成排的孔的形状。将插座插头连接至未使用的垂直或水平连续孔。 可以使用 2 。换句话说,从上面 右起第 i 从右数第th j 第一个洞( 如果我们称之为i,j),

  • (i,j) 和 (i+1,j) (1 ≦ i ≦ H-1, 1 ≦ j ≦ W) 的 2 选择并使用一个孔。
  • (i,j) 和 (i,j+1) (1 ≦ i ≦ H, 1 ≦ j ≦ W-1) 的 2 选择并使用一个孔。

插入插座插头时,多个插座插头不能同时共用同一个孔,或者使用带插座盖的孔(稍后介绍)。

有一天,总统决定让插入插座变得更有趣。N 业务开始时执行以下操作之一 1 我决定做一件事。

  • 未使用的孔 1 选择一个并将出口盖插入该孔中。
  • 出口盖插入的孔 1 选择一个并取下出口盖以将其闲置。

最初,假设所有孔均未使用。

总裁告诉经理,N 参与者被要求记录每个工作日将设备插入电源插座的方式总数,并在最后一天报告他们的发现。组合时,不区分插座插头或插座盖; 1 我从来没有使用过或使用过的东西 1 让我们把它算作一条街道。

然而,经理直到截止日期前才忘记了这一点,并决定从碰巧留下的出口上限历史中查找每天的结果。

如果我们详尽地调查每一个组合,我们似乎无法及时完成,所以开发组的你被要求编写一个程序。


入力

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

H W
N
S_1 T_1
S_2 T_2
:
S_N T_N
  • 1 线表示出口的形状。 2 整数 H (1 ≦ H ≦ 2) 和 W (1 ≦ W ≦ 10^{11}) 用空格分隔。它有一个垂直出口 H 行横 W 表示具有排成一排的孔的形状。
  • 2 行是表示操作时间表的整数。 N (1 ≦ N ≦ 20,000) 给出。
  • 3 在 N 行提供有关操作的信息。其中 i 中,i 代表当天要执行的操作 给出了 2 整数 S_i (1 ≦ S_i ≦ H) 和 T_i (1 ≦ T_i ≦ W) 。这是在当天营业开始时间之前完成的( 若S_i, T_i)未使用,则表示当天营业开始时将插上出水口盖,否则表示将出水口盖取下。 满足

部分点

针对此问题设置了部分分数。 如果正确答案是满足

  • W ≦ 5,000 , N ≦ 3,000 的数据集 如果您正确回答 1 , 如果您对10 点。 如果正确答案是满足
  • W ≦ 100,000 , N ≦ 3,000 的数据集 如果您正确回答 2 的回答正确,除上述之外, 30 点。 如果正确答案是满足
  • 没有附加约束的数据集 通过 3 的回答正确,除上述之外, 60 点。 如果正确答案是满足

出力

N 线输出。 在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