思路

• 行列独立翻转为异或模型：最终单元 $a_{i,j} = r_i \oplus c_j$，其中 $r_i$ 为第 $i$ 行翻转奇偶，$c_j$ 为第 $j$ 列翻转奇偶。只需记录被翻转奇数次的行集合 $R$ 与列集合 $C$，其大小分别为 $|R|$ 与 $|C|$。

• 每一行只有两种形态：

  • 若该行未翻（$r_i=0$），则该行的二进制数为 $V_0$，其中

    • $V_0=\sum_{j\in C} 2^{m-j}\ \bmod MOD$；

  • 若该行被翻（$r_i=1$），该行即为按位取反的 $V_1$，其中

题目内容

有一个 $n$ 行 $m$ 列的网格 $a$ ，我们使用 $a_{i,j}$ 表示网格中从上往下数第 $i$ 行和从左往右数第 $j$ 列的单元格，初始所有单元格中的数字都为 $0$ ，Tk将进行 $k$ 次操作，每次操作两个值 $x,y$ ：

• 当 $x=1$ 时，将第 $y$ 列的所有元素反置。

• 当 $x=2$ 时，将第 $y$ 行的所有元素反置。

所有操作结束后 Tk 将会按照

$a_{1,1},a_{1,2},...,$$a_{1,m},a_{2,1},a_{2,2},...,$$a_{2,m},...,a_{n-1,1},a_{n-1,2},...,$$a_{n-1,m},a_{n,1},$$a_{n,2},...,a_{n,m}$

的顺序依次拼接形成一个二进制数字，Tk 想知道这个二进制数字对应的十进制为多少，输出这个十进制数字(不带前导零)，由于答案可能很大，你只需输出对 $10^9+7$ 取模后的结果即可。

【反置】若当前数字为 $0$ ，反置后为 $1$ ；若当前字符为 $1$ ，反置后为 $0$ 。

输入描述

第一行输入三个整数 $n,m,k(1≦n,m≦10^9,1≦k≦2×10^5)$ 表示网格大小以及 Tk 的操作次数。

接下来 $k$ 行每一行输入两个整数 $x,y(x∈$ {$1,2$} ，当 $x=1$ 时 $1≦y≦m$ ， 当 $x=2$ 时 $1≦y≦n)$ 表示 Tk 的操作。

输出描述

输出一个整数表示拼接形成二进制对应十进制对 $10^9+7$ 取模的结果。

样例1

输入

5 5 4
1 2
2 5
1 3
2 2

输出

13218195