Kyriakos Grizzly got bored from exercising so he decided to paint his rock collection! His collection consists of $N$ rocks which he lays across the ground in a row, numbered $1$ to $N$ from left to right. He also has $C$ colours of paint which he will use to paint the rocks. Exactly $M$ of his $N$ rocks have already been painted (with one of the $C$ colours), in which case they will not be painted again. Kyriakos, being very artistic, realizes that his collection will be more beautiful if each colour used is more spread out. Thus, he will assign his collection a score in the following way:

For every colour $c$ that appears at least once, find the index of the leftmost rock $i$ with colour $c$ and the index of the rightmost rock $j$ with colour $c$. The score is the sum of $j-i$ for all $c$.

If each rock (that hasn't been painted) is painted randomly with a colour from $1$ to $C$, what is the expected value of the score?

Constraints

$1\le N,C\le {10}^9$

$0\le M\le min(N,2\times {10}^5)$

$1\le r_i\le N$

$1\le c_i\le C$

All $r_i$ will be distinct.

Subtask 1 [30%]

$1\le N\le 2\times {10}^5$

Subtask 2 [20%]

$M=0$

Subtask 3 [50%]

No additional constraints.

Note: You must pass subtasks 1 and 2 in order for this subtask to run.

Input Specification

The first line will contain three space-separated integers, $N$, $C$, and $M$.

The next $M$ lines will contain two space-separated integers, $r_i$ and $c_i$, indicating that rock $r_i$ has already been painted with colour $c_i$.

Output Specification

Output one integer, the expected value of the score modulo ${10}^9+7$. More specifically, if the expected value is $\frac{x}{y}$, output $x{y}^{-1}(\mathrm{mod}{10}^9+7)$.

Sample Input 1

5 2 3
1 2
3 1
5 2

Sample Output 1

5

Sample Input 2

7 4 3
2 4
5 2
4 1

Sample Output 2

210937509