题目描述

Ori 和 Sein 已经克服了许多艰难的挑战。他们终于点亮了被遮蔽的灯笼，并找到了 Gumon 印记——通往 Forlorn Ruins 的钥匙。当他们试图打开遗迹之门时……什么也没有发生。

Ori 非常惊讶，但 Sein 很快给出了解释：聪明的 Gumon 决定为大门增加一道额外的防御。

现在有 $n$ 盏拥有 Spirit Tree 光芒的灯。Sein 知道第 $i$ 盏灯的开启和关闭时间，分别为 $l_i$ 和 $r_i$。要打开大门，你需要选择 $k$ 盏灯，使得存在某一时刻这 $k$ 盏灯都处于开启状态。

当 Sein 决定选择哪 $k$ 盏灯时，Ori 很感兴趣：有多少种方式可以选择这样的 $k$ 盏灯，使得大门能够打开？也有可能 Sein 错了，根本不存在这样的 $k$ 盏灯。答案可能很大，请输出答案对 $998\,244\,353$ 取模后的结果。

输入格式

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 3 \cdot 10^5$，$1 \le k \le n$）——灯的总数以及必须同时点亮的灯的数量。

接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le 10^9$），表示第 $i$ 盏灯的开启和关闭时间区间。

输出格式

输出一个整数，表示满足条件的方案数，对 $998\,244\,353$ 取模后的结果。

说明/提示

在第一个测试用例中，有九组 $k$ 盏灯的选择方式：$(1, 2, 3)$，$(1, 2, 4)$，$(1, 2, 5)$，$(1, 2, 6)$，$(1, 3, 6)$，$(1, 4, 6)$，$(2, 3, 6)$，$(2, 4, 6)$，$(2, 6, 7)$。

在第二个测试用例中，$k=1$，所以答案是 3。

在第三个测试用例中，没有任何一对灯满足条件。

在第四个测试用例中，所有灯在时刻 3 都点亮，所以答案是 1。

在第五个测试用例中，有七组 $k$ 盏灯的选择方式：$(1, 2)$，$(1, 3)$，$(2, 3)$，$(2, 4)$，$(3, 4)$，$(3, 5)$，$(4, 5)$。

由 ChatGPT 4.1 翻译

样例

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

9

3 1
1 1
2 2
3 3

3

3 2
1 1
2 2
3 3

0

3 3
1 3
2 3
3 3

1

5 2
1 3
2 4
3 5
4 6
5 7

7