Problem Description

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

Determine how many positive integer sequences \( a \) of length \( n \) exist, where each element \( a_i \) satisfies \( 1 \le a_i \le V \), such that after performing the following operations for \( k = 1, 2, \ldots, m \), the sequence \( a \) is non-decreasing:

• If \( a_{p_k} > a_{q_k} \), swap the values of \( a_{p_k} \) and \( a_{q_k} \).

The answer should be taken 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

A single line containing an integer, representing the answer modulo \( 10^9 + 7 \).

Sample Input and Output

Sample Input #1

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

Sample Output #1

12

Sample Input #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

Sample Output #2

508510094

Notes

[Sample Explanation #1]

For the first sample, the following 12 sequences are valid:

\(\{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\}\).

[Data Range]

This problem is bundled test cases.

• 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 additional constraints.

For all test data, \( 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 relationship between \( p_k \) and \( q_k \) is not guaranteed, and data may include \( p_k = q_k \).

见题面 Input 部分

见题面 Output 部分