配点

満点

120

部分点

30

---

问题文

A君、T君和J先生正在查看地下世界列车的各个运行区间表。J先生注意到一些运行区间可以排列成金字塔形状，并命令A君和T君计算有多少种排列方式。

现在给定$N$个运行区间。请计算有准确$D$个元素的运行区间序列\[ A_1,A_2,...,A_D \]，满足对于任意$i=1,...,D-1$，$(A_i的起点)<(A_{i+1}的起点)$且$(A_{i+1}的终点)< (A_i的终点)$始终成立的排列数量。求不同的运行区间序列数量除以$31,415,926,500$的余数。

---

输入格式

输入按以下格式给出。

$N\\ D\\\\ left_1\\ right_1\\\\ left_2\\ right_2\\\\ ...\\\\ left_N\\ right_N$

其中$N$表示运行区间的数量。$left_i$表示第$i$个运行区间的起点位置，$right_i$表示第$i$个运行区间的终点位置。

输出格式

在一行中输出组合数。

约束条件

• $2 ≤ N ≤ 100000$
• $2 ≤ D ≤ 15$
• $\-10^9 ≤ left_i,\\ right_i ≤ 10^9$
• $left_i < right_i$
• $left_i$和$right_j$互不相同。
• 输入都是整数。

对于该问题，将进行一个包含30个测试用例组的评分。这个组的测试用例还要满足以下约束条件：

• $D=2$

---

输入例子 1

3 2
1 7
2 4
8 10

输出例子 1

1

如图所示，只有由第1个运行区间和第2个运行区间组成的序列满足条件。

图1

---

输入例子 2

5 4
1 10
2 9
3 8
4 7
5 6

输出例子 2

5

由于从5个元素中选择任意4个并重新排列后可以满足条件，所以共有$C(5,4)=5$种方式。

图2

---

输入例子 3

4 2
1 10
2 5
3 4
8 11

输出例子 3

3

---

输入例子 4

4 3
1 7
2 8
3 6
4 5

输出例子 4

2

---

出题人: uwi

---

来源名称

秋之狂欢

---