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)$$$。