[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$。

输入输出样例

输入样例 #1

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

输出样例 #1

90

说明

### 样例解释 #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\%$ 的数据,$1\leq n, m \leq 10^9$,$0\leq k \leq 10^5$,$1 \leq x \leq m$,$1 \leq y \leq n$。