题目内容

一块广告灯阵有 $n$ 行 $m$ 列，初始时每个灯都是熄灭状态，用 0 表示；点亮用 1 表示。

共进行 $k$ 次切换。每次给出两个整数 $x$ 和 $y$：若 $x=1$，则把第 $y$ 列的所有灯取反（0 变 1，1 变 0）；若 $x=2$，则把第 $y$ 行的所有灯取反。

全部切换结束后，将灯阵按行优先顺序（先第一行从左到右，再第二行，以此类推）拼成一个长度为 $n\times m$ 的二进制数，求该数的十进制值对 $10^9+7$ 取模的结果。

约束：行数与列数均不超过 10^9，切换次数不超过 2\times 10^5。

输入描述

第一行包含三个整数 $n$、$m$ 和 $k$，分别表示行数、列数与切换次数。保证 $1 \le n, m \le 10^9$，$1 \le k \le 2 \times 10^5$。 接下来 $k$ 行，每行两个整数 $x$ 和 $y$。若 $x=1$，表示取反第 $y$ 列；若 $x=2$，表示取反第 $y$ 行。保证 $x \in \{1, 2\}$，$1 \le y \le m$ 当 $x=1$，$1 \le y \le n$ 当 $x=2$。

输出描述

输出一个整数，表示行优先拼接得到的二进制数对 $10^9+7$ 取模后的结果。

样例1

输入

1 1 1
2 1

输出

1

说明

只有一盏灯，初始为 0。取反第 1 行后变为 1。 二进制数就是 1，答案为 1。

样例2

输入

1 3 1
1 2

输出

2

说明

一行三列，取反第 2 列后灯态为 0 1 0。 对应二进制数为 2，答案为 2。

样例3

输入

1 1 1
3 2

输出

500000004

说明

按题意模拟计算得到。