P2220 [HAOI2012] Easy Problem

There is a sequence $A$ of length $m$ consisting of positive integers, where every element lies in $[1, n]$. You are given some constraints ($A_x$ cannot be $y$). Let the product of the sequence $A$ be $\prod A$. Compute the sum of the products over all valid sequences. In other words, let $S$ be the set of all valid sequences $\{A, A', \ldots\}$, and compute $$ \sum_{T \in S} \prod T. $$ The answer is taken modulo $10^9 + 7$.

The first line contains three positive integers $n, m, k$. Here, $n$ and $m$ are as described above, and $k$ is the number of constraints. Each of the next $k$ lines contains two positive integers $x, y$, representing the constraint $A_x \ne y$.

Output a single integer on one line: the answer. If there is no valid sequence, output $0$.

### Sample Explanation #1 $A_1$ cannot be $1$, $A_2$ cannot be $2, 3$, and $A_4$ cannot be $3$, so there are the following $12$ possible sequences: | Sequence | Product | | :-: | :-: | | $\{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$ | ### Constraints - For $30\%$ of the testdata, $n \leq 4$, $m \leq 10$, $k \leq 10$. - For another $20\%$ of the testdata, $k = 0$. - For $70\%$ of the testdata, $n, m, k \leq 1000$. - For $100\%$ of the testdata, $1 \leq n, m \leq 10^9$, $0 \leq k \leq 10^5$, $1 \leq x \leq m$, $1 \leq y \leq n$. Translated by ChatGPT 5