题目描述

为了使得大家高兴，小 Q 特意出个自认为的简单题来满足大家，这道简单题描述如下：

有一个数列 $a$，已知对于所有的 $a_i$ 都是 $[1,n]$ 之间的自然数，并且知道对于一些 $a_i$ 不能取哪些值，我们定义一个数列的积为该数列所有元素的乘积。

要求你求出所有可能的数列的积的和 $\bmod (10^9+7)$ 的值，是不是很简单呢？呵呵！

输入格式

第一行三个整数 $n,m,k$，分别表示数列元素的取值范围，数列元素个数，以及已知的限制条数。
接下来 $k$ 行，每行两个正整数 $x,y$ 表示 $a_x$ 的值不能是 $y$。

输出格式

一行一个整数表示所有可能的数列的积的和对 $10^9+7$ 取模后的结果。

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

90

数据规模与约定

对于 $30\%$ 的数据 $n\leq 4$，$m\leq 10$，$k\leq 10$。
另有 $20\%$ 的数据 $k=0$。
对于 $70\%$ 的数据 $n\leq 10^3$，$m\leq 10^3$，$k\leq 10^3$。
对于 $100\%$ 的数据 $n\leq 10^9$，$m\leq 10^9$，$k\leq 10^5$，$1\leq y\leq n$，$1\leq x\leq m$。