Problem Statement

Tempura-kun is on the 1st floor of a building with $N$ floors. This building has $M$ elevators, numbered from 1 to $M$, each with a distinct number. Elevator $i$ stops at each floor from floor $L_i$ to floor $R_i$. Tempura-kun made exactly $k$ moves using these elevators. Here, one "move" specifically means the following procedure.

• Letting $x$ be the current floor, choose one elevator $i$ satisfying $L_i \le x \le R_i$, ride elevator $i$, and get off at floor $y$ satisfying $L_i \le y \le R_i$. Note that $x=y$ is allowed, and in this case he is also regarded as having ridden elevator $i$.

• There exists some $j$ such that the elevators ridden in the $j$-th move are different.
• There exists some $j$ such that the floors he is on after the $j$-th move are different.

Apologies

With the writer's poor knowledge, the solution got TLE when written in Python3. The same code submitted in PyPy3 got AC (about 900 ms).

Input

$N\ M\ K$
$L_1\ R_1$
$L_2\ R_2$
$\vdots$
$L_M\ R_M$

• $1\le N,\ M,\ K\le 3000$
• $1\le L_i \le R_i \le N$
• All inputs are integers.

Output

Output the number of ways of moving, modulo $10^9+7$, on one line.

Sample

2 2 2
1 2
1 2

8

5 1 5
2 2

0

8 6 10
2 7
1 8
2 8
1 8
2 8
4 6

70138606