Description

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

The answer is taken modulo $10^9 + 7$.

Input Format

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 Format

Output a single integer on one line: the answer.

If there is no valid sequence, output $0$.

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

90

Hint

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:

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