题目描述

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

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

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

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

输入格式

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

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

输出格式

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

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

3 4 5
1 1
1 1
2 2
2 3
4 3

90

提示

样例解释 #1

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

数据范围

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

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

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

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