Problem Description

Farmer John is hiring a new herd leader for his cows. For this purpose, he interviewed $N$ ($2\le N\le 10^9$) cows for the position. After each interview, he assigns a "competency" score $c_i$ within the range $1$ to $C$ ($1\le C\le 10^4$), related to their leadership abilities.

Since Farmer John interviewed so many cows, he has forgotten all the competency scores. However, he does remember $Q$ ($1\le Q\le \min(N−1,100)$) pairs of numbers $(a_i,h_i)$, where cow $h_i$ is the first cow with a strictly higher competency score than cows $1$ to $a_i$ (thus $1\le a_i<h_i\le N$).

Farmer John now tells you these $Q$ pairs $(a_i,h_i)$. Please help him count how many competency score sequences are consistent with this information! The input guarantees that there is at least one such sequence. Since this number might be very large, output the value modulo $10^9+7$.

Input Format

The first line of input contains $N$, $Q$, and $C$.

The following $Q$ lines each contain a pair $(a_i,h_i)$. The input guarantees that all $a_i$ are distinct.

Output Format

Output the number of competency score sequences consistent with Farmer John's memory, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

6 2 3
2 3
4 5

Sample Output #1

6

Sample Input #2

10 1 20
1 3

Sample Output #2

399988086

Notes/Hints

Sample Explanation 1

The following six sequences are the only ones consistent with Farmer John's memory:

$1\ 1\ 2\ 1\ 3\ 1$
$1\ 1\ 2\ 1\ 3\ 2$
$1\ 1\ 2\ 1\ 3\ 3$
$1\ 1\ 2\ 2\ 3\ 1$
$1\ 1\ 2\ 2\ 3\ 2$
$1\ 1\ 2\ 2\ 3\ 3$

Sample Explanation 2

Ensure the output is modulo $10^9+7$.

Test Case Properties

• Test cases $3-4$: $N\le 10$ and $Q,C\le 4$.
• Test cases $5-7$: $N,C\le 100$.
• Test cases $8-10$: $N\le 2000$ and $C\le 200$.
• Test cases $11-15$: $N,C\le 2000$.
• Test cases $16-20$: No additional restrictions.

见题面 Input 部分

见题面 Output 部分