← 返回题目列表

Codeforces · 1420/D

D. 营救尼贝尔!

中文机器翻译题面 查看原题

Ori 和 Sein 克服了许多困难的挑战。他们终于点燃了笼罩灯笼,并找到了古门封印,这是通往荒废遗迹的钥匙。当他们试图打开通往废墟的门时……什么也没发生。

奥里很惊讶,但塞恩很快给出了解释:聪明的古蒙决定对门进行额外的防御。

有$$$n$$$带有灵树之光的灯。 Sein 知道第 $$$i$$$ 灯的打开和关闭时间 - 分别为 $$$l_i$$$ 和 $$$r_i$$$。要打开门,您必须选择 $$$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$$$ 为模。

示例

输入 #1

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

输出 #1

9

输入 #2

3 1
1 1
2 2
3 3

输出 #2

3

输入 #3

3 2
1 1
2 2
3 3

输出 #3

0

输入#4

3 3
1 3
2 3
3 3

输出#4

1

输入 #5

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

输出 #5

7

注意

在第一个测试用例中,有九组 $$$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)$$$。