为了使得大家高兴，小Q特意出个自认为的简单题（easy）来满足大家，这道简单题是描述如下：
有一个数列 $A$ 已知对于所有的 $A[i]$ 都是 $1$~$n$ 的自然数，并且知道对于一些 $A[i]$ 不能取哪些值，我们定义一个数列的积为该数列所有元素的乘积，要求你求出所有可能的数列的积的和 $\bmod 1000000007$ 的值，是不是很简单呢？呵呵！
第一行三个整数 $n,m,k$ 分别表示数列元素的取值范围，数列元素个数，以及已知的限制条数。
接下来 $k$ 行，每行两个正整数 $x,y$ 表示 $A[x]$ 的值不能是 $y$。
一行一个整数表示所有可能的数列的积的和对 $1000000007$ 取模后的结果。如果一个合法的数列都没有，答案输出 $0$。
3 4 5 1 1 1 1 2 2 2 3 4 3
90
$30\%$ 的数据 $n \le 4,m \le 10,k \le 10$
另有 $20\%$ 的数据 $k=0$
$70\%$ 的数据 $n \le 1000,m \le 1000,k \le 1000$
$100\%$ 的数据 $n \le 10^9,m \le 10^9,k \le 10^5,1 \le y \le n,1 \le x \le m$
Comet OJ