Background

Original link: https://oier.team/problems/S2D。

Problem Description

Given $n, V$ and a sequence of length $m$: $(p_1, q_1), (p_2, q_2), \dots, (p_m, q_m)$.

Find how many positive integer sequences $a$ of length $n$ satisfy that every element $a_i$ meets $1 \le a_i \le V$, and after performing the following operation in order for $k = 1, 2, \dots, m$, the sequence $a$ becomes non-decreasing:

• If $a_{p_k} > a_{q_k}$, swap the values of $a_{p_k}$ and $a_{q_k}$.

Output the answer modulo $10^9 + 7$.

Input Format

The first line contains three integers $n, V, m$.

The next $m$ lines each contain two integers $p_k, q_k$.

Output Format

Output one integer, the result modulo $10^9 + 7$.

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

12

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

Hint

Sample Explanation #1

For the first sample, there are $12$ valid sequences:

$\{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\}$。

Constraints

This problem uses bundled testdata.

• Subtask 0 (8 pts): $n \le 6$, $V \le 8$, $m \le 50$.
• Subtask 1 (31 pts): $n \le 8$.
• Subtask 2 (37 pts): $n \le 15$.
• Subtask 3 (24 pts): no special constraints.

For all testdata, $1 \le n \le 18$, $1 \le V \le 10^9$, $1 \le m \le 500$, $1 \le p_k, q_k \le n$. Note that the relative order of $p_k$ and $q_k$ is not guaranteed, and the data may contain $p_k = q_k$.

Translated by ChatGPT 5