Problem Description

Little T is studying the events that occurred during a certain period. Through observation, there are \( n \) events numbered from \( 1 \) to \( n \) that happened sequentially within this period, with the \( i \)-th event being \( p_i \). The permutation \( p \) describing the order of these events can be called the timeline of this period.

Suddenly, the evil creature Little S attacked this timeline, changing the order of the \( n \) events \( p \) to a permutation randomly chosen with equal probability from all permutations of length \( n \). Not only that, Little S also cut the timeline with scissors, dividing the permutation \( p \) into \( (k + 1) \) segments by performing \( k \) operations.

Specifically, during the \( i \)-th operation, the permutation \( p \) and all previously inserted cut points form a sequence of length \( (n + i - 1) \). This sequence includes \( (n + i) \) insertion positions, including between every two adjacent elements and at the beginning and end of the sequence. Little S will randomly select one of these insertion positions to insert a new cut point. Finally, Little S will cut the sequence at the \( k \) inserted cut points, dividing the permutation \( p \) into \( (k + 1) \) segments. Some of these segments may be empty.

To save the timeline that is about to be destroyed, Little T decides to reassemble these \( (k + 1) \) segments into a permutation of length \( n \) in a certain order, forming a new timeline. However, due to the logical relationships between events, there are certain precedence requirements for the occurrence times of events. After research, it is found that there are \( m \) precedence requirements \( (u, v) \), requiring that the occurrence time of event \( u \) must be before that of event \( v \). That is, the position of \( u \) in the timeline must be before \( v \).

Please design a program to calculate the probability that there exists at least one way to rearrange these \( (k + 1) \) segments and reassemble them into a new timeline such that all \( m \) precedence requirements for the occurrence times of events are satisfied.

To avoid precision errors, please output the result modulo \( 10^9 + 7 \). Formally, it can be proven that the answer can be represented as a simplified fraction \( \frac{p}{q} \). Please 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 conditions of the problem.

Input Format

The first line contains three integers \( n \), \( m \), and \( k \), describing the number of events, the number of precedence requirements, and the number of cutting operations performed by Little S, respectively.

The next \( m \) lines each contain two integers \( u \) and \( v \), representing a precedence requirement for the occurrence times of events.

Output Format

Output a single integer, representing the desired answer.

Sample Input and Output

Sample Input #1

2 1 1
1 2

Sample Output #1

666666672

Sample Input #2

3 0 2

Sample Output #2

1

Sample Input #3

4 4 4
1 2
1 3
1 4
2 4

Sample Output #3

937500007

Notes/Hints

[Sample 1 Explanation]

If the occurrence time of event \( 1 \) is earlier than that of event \( 2 \), then any reassembly is a feasible solution and will satisfy the requirement. Otherwise, only if the cut point is between the occurrence times of events \( 1 \) and \( 2 \) can the requirement be satisfied. The answer is \( \frac{1}{2} + \frac{1}{2} \times \frac{1}{3} = \frac{2}{3} \).

[Sample 2 Explanation]

There are no precedence requirements for the occurrence times of events, so any reassembly is a feasible solution, and the answer is \( 1 \).

[Subtasks]

For all test data,

• \( 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 there are no two identical pairs \( (u, v) \).

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

Special Property B: For all precedence requirements \( (u, v) \), \( u = 1 \).

见题面 Input 部分

见题面 Output 部分