Cowmpetency

문제

Farmer John is hiring a new herd leader for his cows. To that end, he has interviewed $NN$ ($2\le N\le {10}^{9}2\; \backslash leq\; N\; \backslash leq\; 10^9$) cows for the position. After each interview, he assigned an integer "cowmpetency" score to the candidate ranging from $11$ to $CC$ ($1\le C\le {10}^{4}1\; \backslash leq\; C\; \backslash leq\; 10^4$) that is correlated with their leadership abilities.

Because he has interviewed so many cows, Farmer John has forgotten all of their cowmpetency scores. However, he does remembers $QQ$ ($1\le Q\le \min (N-1,100)1\; \backslash leq\; Q\; \backslash leq\; \backslash min(N\; -\; 1,\; 100)$) pairs of numbers $(a_i,h_i)(a\_i,\; h\_i)$ where cow $h_{i}h\_i$ was the first cow with a strictly greater cowmpetency score than cows $11$ through $a_{i}a\_i$ (so ).

Farmer John now tells you the $QQ$ pairs of $(a_i,h_i)(a\_i,\; h\_i)$. Help him count how many sequences of cowmpetency scores are consistent with this information! It is guaranteed that there is at least one such sequence. Because this number may be very large, output its value modulo ${10}^9+710^9\; +\; 7$.

입력

The first line contains $NN$, $QQ$, and $CC$.

The next $QQ$ lines each contain a pair $(a_i,h_i)(a\_i,\; h\_i)$. It is guaranteed that all $a_{j}a\_j$ are distinct.

출력

The number of sequences of cowmpetency scores consistent with what Farmer John remembers, modulo ${10}^9+710^9+7$.