说明

时间限制：1 Sec 内存限制：256 MB 输入文件：lift.in 输出文件：lift.out

小明在一栋 $N$ 层大楼的 $1$ 楼。大楼里有 $M$ 部电梯，编号为 $1$ 到 $M$。第 $i$ 部电梯只停靠 $L_i$ 层到 $R_i$ 层之间的所有楼层。

小明使用这些电梯，恰好进行了 $K$ 次移动。

一次“移动”定义为如下操作：

- 设当前在 $x$ 层，选择一部满足 $L_i \le x \le R_i$ 的电梯 $i$，乘坐它并在满足 $L_i \le y \le R_i$ 的某一层 $y$ 下电梯。

- 即使 $x=y$（原地不动），也视为乘坐了一次电梯。

求：经过 $K$ 次移动后，小明恰好位于 $N$ 层的移动方案总数，对 $10^9+7$ 取模。

两种方案视为不同，当且仅当满足以下至少一条：

- 存在某一次 $j$，第 $j$ 次乘坐的电梯不同

- 存在某一次 $j$，第 $j$ 次移动后所在的楼层不同

输入格式

第一行三个整数 $N,M,K$。

接下来 $M$ 行，第 $i$ 行两个整数 $L_i,R_i$。

输出格式

输出方案总数对 $10^9+7$ 取模的结果。

样例

样例 1

2 2 2
1 2
1 2

8

样例说明：

将“乘坐电梯 $i$ 到 $j$ 层”记作 $(i,j)$，合法方案共 $8$ 种：

- $(1,1) → (1,2)$

- $(1,1) → (2,2)$

- $(2,1) → (1,2)$

- $(2,1) → (2,2)$

- $(1,2) → (1,2)$

- $(1,2) → (2,2)$

- $(2,2) → (1,2)$

- $(2,2) → (2,2)$

注意：可以只乘坐电梯不移动，也可能有多部功能完全一样的电梯。

样例 2

5 1 5
2 2

0

样例说明：

不存在能从 $1$ 楼乘坐的电梯，也不存在能在 $5$ 楼下电梯的电梯。

只能停在 $2$ 楼、完全无法移动的电梯有什么意义呢？

样例 3

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

70138606

样例说明：

请对 $10^9+7$ 取模后输出。

数据范围

对于 36% 的数据，$N,M,K \le 300$。

对于 100% 的数据，$1 \le N,M,K \le 3000$，$1 \le L_i \le R_i \le N$。