Counting Sorted Sequences after a Comparator Network

We are given two integers (n) and (V) and a sequence of (m) comparators described by pairs ((p_1,q_1), (p_2,q_2), \dots, (p_m,q_m)). Consider a positive integer sequence (a = (a_1,a_2,\dots,a_n)) with (1 \le a_i \le V) for all (i). We then perform the following operations in order for (k = 1,2,\dots,m):

[ \text{if } a_{p_k} > a_{q_k} \text{ then swap } a_{p_k} \text{ and } a_{q_k}, ]

Let the final sequence be (b). We require that (b) is non–decreasing, i.e.

[ b_1 \le b_2 \le \dots \le b_n. ]

Your task is to count the number of initial sequences (a) for which, after processing all comparators, the resulting sequence is sorted in non–decreasing order. Since the answer can be large, output it modulo (10^9+7).

Note that the swap operations act as comparators (or conditional swaps) forming a comparator network. For example, if (n=2) and the only comparator is ((1,2)), then regardless of (a_1,a_2) the final sequence becomes ((\min(a_1,a_2),\max(a_1,a_2))) which is sorted. However, for other networks the property may hold only for some inputs.

inputFormat

Input is given as follows:

• The first line contains two integers \(n\) and \(V\).
• The second line contains an integer \(m\), the number of comparators.
• The next \(m\) lines each contain two integers \(p_k\) and \(q_k\) (1–indexed) representing the positions that will be compared and possibly swapped.

It is guaranteed that \(1 \le p_k,q_k \le n\) for all \(k\).

outputFormat

Output one integer: the number of initial sequences (a) such that after executing all operations the resulting sequence is non–decreasing. Print the answer modulo (10^9+7).

sample

2 3
1
1 2

9

</p>