【MX-S2-T4】换
题目描述
给定 $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$ 取模后的结果。
输入输出样例
输入样例 #1
3 3 5
3 2
1 3
1 2
2 3
2 1输出样例 #1
12输入样例 #2
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
输出样例 #2
508510094说明
**【样例解释 \#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\}$。
**【数据范围】**
**本题采用捆绑测试。**
- Subtask 0（8 pts）：$n\le6$，$V\le 8$，$m \le 50$。
- Subtask 1（31 pts）：$n \le 8$。
- Subtask 2（37 pts）：$n \le 15$。
- Subtask 3（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$。