Problem Description

T is studying the events that happened during a certain period of time. After observation, there are $n$ events numbered from $1$ to $n$ that occur in this period one by one in some order, where the $i$-th event to occur is $p_i$. This permutation $p$ that describes the order in which events occur is called the timeline of this period.

Suddenly, the evil creature S attacked this timeline and changed the order $p$ into a permutation chosen uniformly at random from all permutations of length $n$. Moreover, S cut the timeline with scissors: by performing $k$ operations, S split the permutation $p$ into $(k + 1)$ segments.

More specifically, when S performs the $i$-th operation, the permutation $p$ together with all previously inserted cut points forms a sequence of length $(n + i - 1)$. This sequence has $(n + i)$ insertion positions in total: between every pair of adjacent elements, and also at the beginning and the end of the sequence. S will choose one of these insertion positions uniformly at random and insert a new cut point. Finally, S cuts the sequence at the $k$ inserted cut points, splitting the permutation $p$ into $(k + 1)$ sequences. Some of these $(k + 1)$ sequences may be empty.

To save this timeline that is about to be destroyed, T decides to concatenate these $(k + 1)$ sequences in some order to form a new permutation of length $n$, thus creating a new timeline. However, due to certain logical relationships among events, there are precedence requirements on their occurrence times. After research, there are $m$ precedence requirements $(u, v)$, requiring that event $u$ must occur before event $v$. That is, the position of $u$ in the timeline must be before $v$.

Please write a program to compute the probability that there exists at least one way to reorder these $(k + 1)$ segments and concatenate them into a new timeline such that all $m$ precedence requirements are satisfied.

To avoid precision errors, output the answer modulo $10^9 + 7$. Formally, it can be proven that the answer can be expressed as an irreducible fraction $\frac{p}{q}$. You need to output an integer $x$ such that $0 \le x < 10^9+7$ and $qx \equiv p \pmod {10^9+7}$. It can be proven that such an $x$ always exists under the constraints of this problem.

Input Format

The first line contains three integers $n, m, k$, describing the number of events, the number of precedence requirements among events, and the number of cut operations performed by S.

The next $m$ lines each contain two integers $u, v$, representing one precedence requirement.

Output Format

Output one line with one integer, representing the required answer.

2 1 1
1 2

666666672

3 0 2

1

4 4 4
1 2
1 3
1 4
2 4

937500007

Hint

[Sample 1 Explanation]

If event $1$ occurs earlier than event $2$, then no matter how you concatenate the segments, it is always feasible and the requirement can always be satisfied. Otherwise, the requirement can be satisfied only if the cut position lies between the occurrence times of event $1$ and event $2$. The answer is $\frac{1}{2}+\frac{1}{2}\times \frac{1}{3}=\frac{2}{3}$.

[Sample 2 Explanation]

There are no precedence requirements between events, so any concatenation is feasible. The answer is $1$.

[Sample 4]

See timeline4.in/ans in the attachment.

[Sample 5]

See timeline5.in/ans in the attachment.

This sample satisfies Special Property B in the Constraints.

[Sample 6]

See timeline6.in/ans in the attachment.

This sample satisfies Special Property A in the Constraints.

[Sample 7]

See timeline7.in/ans in the attachment.

[Subtasks]

For all testdata,

• $1 \le n \le 15$,
• $0 \le m \le \frac{n(n-1)}{2}$, $0 \le k \le n$,
• $1 \le u < v \le n$, and it is guaranteed that there are no two identical pairs $(u,v)$.

Special Property A: For each event $x$, there exists at most one precedence requirement $(u, v)$ such that $v = x$.

Special Property B: For all precedence requirements $(u, v)$, it holds that $u = 1$.

Translated by ChatGPT 5