[HAOI2012] 容易题

有一个长度为 $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$。

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$ 种： | 数列 | 积 | | :-: | :-: | | $\{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\%$ 的数据，$1\leq n, m \leq 10^9$，$0\leq k \leq 10^5$，$1 \leq x \leq m$，$1 \leq y \leq n$。