解题思路

先把题意抽象一下。

初始时网格全是 $0$。 一次操作只会反转一整行或一整列，因此最终某个位置 $(i,j)$ 的值只和两件事有关：

• 第 $i$ 行被反转了奇数次还是偶数次
• 第 $j$ 列被反转了奇数次还是偶数次

题目内容

有一个 $n$ 行 $m$ 列的网格，初始所有单元格为 $0$ 。进行 $k$ 次操作，每次反置某一行或某一列($0$ 变 $1$，$1$ 变 $0$)。

所有操作结束后，将网格按行优先顺序拼接为一个二进制数，输出其十进制值对 $10^9+7$ 取模的结果。

输入描述

第一行三个整数 $n,m,k(1≤n,m≤10^9,1≤k≤2×10^5)$。接下来 $k$ 行每行两个整数 $x,y$：$x=1$ 表示反置第列，$x=2$ 表示反置第 $y$ 行。

输出描述

输出一个整数，结果对 $10^9+7$ 取模。

样例1

输入

5 5 4
1 2
2 5
1 3
2 2

输出

13218195