問題文
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