Cowmpetency

Time limit2sMemory limit1024 MB

Summary

Count the score sequences of N cows, each score from 1 to C, that satisfy each pair where cow h is the first with a score above cows 1 through a, modulo 10^9+7.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Prefix sum
Solved: No attempts yet

Problem

Farmer John is hiring a new herd leader for his cows. He has interviewed $N$ cows for the position ( $2 \leq N \leq 10^9$ ). After each interview, he gave the candidate a cowmpetency score, an integer from $1$ to $C$ ( $1 \leq C \leq 10^4$ ), which reflects that cow's leadership ability.

Farmer John has forgotten every cowmpetency score. He does remember $Q$ pairs $(a_i, h_i)$ ( $1 \leq Q \leq \min(N - 1, 100)$ ): cow $h_i$ was the first cow with a strictly greater cowmpetency score than cows $1$ through $a_i$ , so $1 \leq a_i < h_i \leq N$ .

You are given the $Q$ pairs. Count the sequences of cowmpetency scores that are consistent with this information. At least one such sequence is guaranteed to exist. Output the count modulo $10^9+7$ .

Input

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

Each of the next $Q$ lines contains a pair $(a_i, h_i)$ . All $a_j$ are distinct.

Output

Print the number of consistent sequences of cowmpetency scores modulo $10^9+7$ .

Examples2

Example 1
Input
```
6 2 3
2 3
4 5
```
Expected output
```
6
```
Example 2
Input
```
10 1 20
1 3
```
Expected output
```
399988086
```