_After spending a long time immersed in researching "Chicken Jockeys," Steve decided to take a break from the world of creatures and shift his focus to something new… GRAPHS! But since he lives in the world of Minecraft—where everything is made of square blocks—instead of drawing graphs with dots and lines like usual, Steve decided to build them using squares._
Steve builds $m$ squares on the coordinate plane. The $i$-th square is defined by two corners: its bottom-left corner at $(x_i, x_i)$ and its top-right corner at $(y_i, y_i)$. These squares are axis-aligned, and the center of each square represents a vertex in Steve’s graph. He connects the centers of any two squares with an undirected edge if the two squares share any point in common (overlap or touch at least one point). In order to keep the graph safe from mobs, Steve only builds squares that are completely contained within a larger square area with bottom-left corner at $(1, 1)$ and top-right corner at $(n, n)$. After building his graph, Steve wonders: How many ways are there to choose a set of exactly $k$ squares such that the subgraph formed by connecting their centers is a complete graph?
### Input
- The first line contains $3$ positive integers $n, m, k$, separated by a single space.
- The next $m$ lines each contain two positive integers $x_i, y_i$, where the $i$-th line describes the $i$-th square.
### Output
- Output the answer modulo $10^9+7$.
### Constraint
- $1 \le n,m,k \le 10^5$
- $1 \le x_i \le y_i \le n,1 \le i \le m$
### Example
Input
```
6 3 2
1 3
2 5
1 6
```
Output:
```
3
```
### Explanation
In the first test case, Steve has $3$ valid ways to choose the squares:
- Option $1$: choose square $1$ and $2$.
- Option $2$: choose square $2$ and $3$.
- Option $3$: choose square $1$ and $3$.
