Little T is studying events that occurred over a certain period. Observations show that $n$ events, numbered $1 \sim n$, occurred sequentially during this period, and the $i$-th event to occur was event $p_i$. This permutation $p$, which describes the order of events, can be called the "timeline" of this period.

Suddenly, the evil creature Little S attacked this timeline, changing the occurrence order $p$ of these $n$ events to a permutation chosen uniformly at random from all permutations of length $n$. Furthermore, Little S used scissors to cut the timeline, performing $k$ operations to divide the permutation $p$ into $(k+1)$ segments.

Specifically, when Little S performs the $i$-th operation, the permutation $p$ and all previously inserted cut points form a sequence of length $(n+i-1)$. This sequence has $(n+i)$ insertion positions, including those between all adjacent elements and at the beginning and end of the sequence. Little S chooses one of these insertion positions uniformly at random and inserts a new cut point. Finally, Little S cuts the sequence at the $k$ inserted cut points, dividing the permutation $p$ into $(k+1)$ segments. These $(k+1)$ segments may include empty sequences.

To save this timeline from destruction, Little T decides to reassemble these $(k+1)$ segments in some order to form a new permutation of length $n$, creating a new timeline. However, due to certain logical relationships between events, there are requirements on the relative order of event occurrences. Research shows 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 design a program to calculate the probability that there exists at least one way to reorder these $(k+1)$ segments and splice them into a new timeline such that all $m$ precedence requirements are satisfied.

To avoid precision errors, please output the result modulo $10^9+7$. Formally, it can be proven that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, and you should 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 problem conditions.

Input

Read data from the file timeline.in.

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

The next $m$ lines each contain two integers $u, v$, representing a precedence requirement that event $u$ must occur before event $v$.

Output

Output to the file timeline.out.

Output a single integer representing the required answer.

Examples

Input 1

2 1 1
1 2

Output 1

666666672

Input 2

3 0 2

Output 2

1

Input 3

4 4 4
1 2
1 3
1 4
2 4

Output 3

937500007

Input 4

See timeline/timeline4.in and timeline/timeline4.ans in the contestant directory.

Input 5

See timeline/timeline5.in and timeline/timeline5.ans in the contestant directory. This set of examples satisfies special property B.

Input 6

See timeline/timeline6.in and timeline/timeline6.ans in the contestant directory. This set of examples satisfies special property A.

Input 7

See timeline/timeline7.in and timeline/timeline7.ans in the contestant directory.

Constraints

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$, it is guaranteed that no two pairs $(u, v)$ are identical.

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$ is satisfied.

Figure 1. Illustration of the cutting, reordering, and splicing process to satisfy precedence requirements.