题目描述

给定 $n,V$ 和一个长为 $m$ 的序列 $(p_1,q_1),(p_2,q_2),\dots,(p_m,q_m)$。

请求出有多少长度为 $n$ 的正整数序列 $a$，其所有元素 $a_i$ 满足 $1\le a_i\le V$，将其按 $k=1,2,\dots,m$ 依次执行如下操作后，$a$ 不降：

• 若 $a_{p_k}>a_{q_k}$，则交换 $a_{p_k}$ 与 $a_{q_k}$ 的值。

答案对 $10^9+7$ 取模。

输入格式

第一行三个整数 $n,V,m$。

接下来 $m$ 行，每行两个整数 $p_k,q_k$。

输出格式

一行一个整数表示答案对 $10^9+7$ 取模后的结果。

样例

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

12

样例 1 解释

对于第一组样例，有以下 $12$ 种符合条件的序列：

$\{1,1,1\}$，$\{1,1,2\}$，$\{1,1,3\}$，$\{1,2,1\}$，$\{1,3,1\}$，$\{2,1,1\}$，$\{2,2,2\}$，$\{2,2,3\}$，$\{2,3,2\}$，$\{3,1,1\}$，$\{3,2,2\}$，$\{3,3,3\}$。

8 900000754 20
5 5
1 2
3 2
1 8
4 8
5 8
3 4
3 7
5 7
3 4
6 8
1 5
7 8
7 8
5 7
1 8
3 8
3 8
5 6
3 8

508510094

数据范围

本题采用捆绑测试。

• Subtask 1（8 pts）：$n\le6$，$V\le 8$，$m \le 50$。
• Subtask 2（31 pts）：$n \le 8$。
• Subtask 3（37 pts）：$n \le 15$。
• Subtask 4（24 pts）：无特殊限制。

对于所有测试数据，$1\le n\le 18$，$1\le V\le 10^9$，$1\le m\le 500$，$1\leq p_k,q_k\leq n$，注意不保证 $p_k$ 和 $q_k$ 的大小关系，且数据可能存在 $p_k=q_k$。