行列独立翻转为异或模型:最终单元 ai,j=ri⊕cj,其中 ri 为第 i 行翻转奇偶,cj 为第 j 列翻转奇偶。只需记录被翻转奇数次的行集合 R 与列集合 C,其大小分别为 ∣R∣ 与 ∣C∣。
每一行只有两种形态:
若该行未翻(ri=0),则该行的二进制数为 V0,其中
若该行被翻(ri=1),该行即为按位取反的 V1,其中
有一个 n 行 m 列的网格 a ,我们使用 ai,j 表示网格中从上往下数第 i 行和从左往右数第 j 列的单元格,初始所有单元格中的数字都为 0 ,Tk将进行 k 次操作,每次操作两个值 x,y :
当 x=1 时,将第 y 列的所有元素反置。
当 x=2 时,将第 y 行的所有元素反置。
所有操作结束后 Tk 将会按照
a1,1,a1,2,...,a1,m,a2,1,a2,2,...,a2,m,...,an−1,1,an−1,2,...,an−1,m,an,1,an,2,...,an,m
的顺序依次拼接形成一个二进制数字,Tk 想知道这个二进制数字对应的十进制为多少,输出这个十进制数字(不带前导零),由于答案可能很大,你只需输出对 109+7 取模后的结果即可。
【反置】若当前数字为 0 ,反置后为 1 ;若当前字符为 1 ,反置后为 0 。
第一行输入三个整数 n,m,k(1≦n,m≦109,1≦k≦2×105) 表示网格大小以及 Tk 的操作次数。
接下来 k 行每一行输入两个整数 x,y(x∈ {1,2} ,当 x=1 时 1≦y≦m , 当 x=2 时 1≦y≦n) 表示 Tk 的操作。
输出一个整数表示拼接形成二进制对应十进制对 109+7 取模的结果。
输入
5 5 4
1 2
2 5
1 3
2 2
输出
13218195