题目描述

有一个长度为 $m$ 的正整数数列 $A$，满足 $\forall i \in A, i \in [1, n]$。

现在给定一些限制（$A_x$ 不能为 $y$）。设数列 $A$ 的积为 $\prod A$，求所有可能数列的积相加起来的和。

换言之，令 $S$ 为所有可能的数列情况 $\{A, A', \ldots\}$，求

$\sum_{T \in S} \prod T$

答案对 $10^9 + 7$ 取模。

输入格式

第一行三个正整数 $n, m, k$。$n, m$ 如题目所示，$k$ 表示限制的条数。

接下来 $k$ 行，每行两个正整数 $x, y$ 表示限制 $A_x \neq y$。

输出格式

一行一个正整数表示答案。

如果没有任何合法数列，输出 $0$。

提示

样例解释 #1

$A_1$ 不能取 $1$，$A_2$ 不能取 $2, 3$，$A_3$ 不能取 $3$，所以可能的数列有以下 $12$ 种：

数列	积
$\{2, 1, 1, 1\}$	$2$
$\{2, 1, 1, 2\}$	$4$
$\{2, 1, 2, 1\}$	$4$
$\{2, 1, 2, 2\}$	$8$
$\{2, 1, 3, 1\}$	$6$
$\{2, 1, 3, 2\}$	$12$
$\{3, 1, 1, 1\}$	$3$
$\{3, 1, 1, 2\}$	$6$
$\{3, 1, 2, 1\}$	$6$
$\{3, 1, 2, 2\}$	$12$
$\{3, 1, 3, 1\}$	$9$
$\{3, 1, 3, 2\}$	$18$

数据范围

对于 $30\%$ 的数据，$n \leq 4, m \leq 10, k \leq 10$。

对于另外 $20\%$ 的数据，$k = 0$。

对于 $70\%$ 的数据，$n, m, k \leq 1000$。

对于 $100\%$ 的数据，$n, m \leq 10^9, k \leq 10^5, 1 \leq x \leq m, 1 \leq y \leq n$。