Rescuing the Timeline

Little T is studying a timeline during which events occur. There are (n) events labeled from (1) to (n) that occur in order; the (i)th occurred event is (p_i). The permutation (p = [p_1, p_2, \ldots, p_n]) is called the timeline.

Suddenly, the evil creature Little S attacks the timeline. It randomizes the ordering — replacing (p) with a permutation uniformly chosen among all (n!) possibilities. Moreover, Little S inserts cut points into the timeline. Starting from the original permutation, Little S performs (k) operations. In the (i)th operation, consider the current sequence (which has length (n+i-1)) and its (n+i) gaps (including before the first element and after the last element). Little S chooses one gap uniformly at random and inserts a new cut marker there. Finally, the sequence is cut at exactly the positions where the markers were inserted, splitting (p) into (k+1) pieces (some pieces may be empty).

In order to save the dying timeline, Little T plans to reorder the (k+1) pieces arbitrarily (keeping the relative order of events inside each piece unchanged) to form a new permutation of length (n). However, between events there are precedence constraints. In total there are (m) constraints, each specified as a pair ((u,v)) meaning that event (u) must occur before event (v) in the final timeline.

A reordering (i.e. a way to permute the (k+1) pieces and concatenate them) is considered valid if after reordering all (m) constraints are satisfied. Note that if two events end up in different pieces, their order can be arbitrarily rearranged by reordering pieces; conversely, if two events lie in the same piece, their relative order is fixed as in the original permutation (p). Therefore, for each constraint ((u,v)) that is violated by (p) (i.e. if in (p) we have (u) occurring after (v)) the violation can be "fixed" by ensuring that event (u) and (v) are in different pieces; equivalently, there must be at least one cut inserted in the interval between (v) and (u) in (p).

Let us define the following: For a given permutation (p) (which is chosen uniformly at random from all (n!) possibilities) and for a given distribution of cut markers among the (n+1) gaps (i.e. an interleaving of (p) with (k) identical markers chosen uniformly among all (C(n+k, k)) possibilities), the outcome is valid if and only if for every constraint ((u,v)) for which (u) appears after (v) in (p) there is at least one marker placed in one of the gaps between (v) and (u) (note that gaps corresponding to the positions between consecutive elements of (p) are the only ones that matter).

Your task is to compute the probability (over the random choice of (p) and the random insertion of markers) that there exists at least one way to reorder the (k+1) pieces into a valid timeline satisfying all constraints. To avoid precision issues, output the answer in the following modular form. It is guaranteed that the answer can be written as an irreducible fraction (\frac{P}{Q}). Find an integer (x) with (0 \le x < 10^9+7) satisfying [ Qx \equiv P \pmod{10^9+7}. ] It can be shown that such an (x) always exists under the given conditions.

Note on the randomness of the marker insertion: One may show that the final outcome is equivalent to choosing a random interleaving of (p) with (k) identical markers (i.e. inserting the (k) markers into the (n+1) available gaps with all (C(n+k, k)) possibilities equally likely). Only the markers inserted into the (n-1) internal gaps (i.e. those between two consecutive elements of (p)) can influence whether a violation is fixed or not.

Input/Output summary:

• You are given three integers \(n, k, m\).
• Then \(m\) lines follow, each contains two integers \(u\) and \(v\) indicating that event \(u\) must occur before event \(v\) in the final timeline.
• Output one integer \(x\) satisfying the modular condition described above.

Constraints:

• \(1 \le n \le 8\) (so that a brute force solution is possible).
• \(0 \le k \le 10\).
• \(0 \le m \le n(n-1)/2\).

inputFormat

The first line contains three integers (n, k, m). Each of the next (m) lines contains two integers (u) and (v), representing a precedence constraint that event (u) must occur before event (v).

outputFormat

Output one integer (x) with (0 \le x < 10^9+7) such that if the answer is (\frac{P}{Q}) in lowest terms, then (Qx \equiv P \pmod{10^9+7}).

sample

2 1 1
1 2

666666672