D. Спасти Нибель!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Преодолев множество сложных испытаний, Ори и Сейн наконец-то зажгли Укрытый Светильник и нашли Печать Гумон, ключ к Руинам Форлорна! Когда же они наконец вставили Печать в дверь... ничего не произошло.

Ори очень этому удивился, но Сейн быстро все объяснил: хитрые Гумон решили наложить дополнительную защиту на дверь.

На двери расположено $$$n$$$ светильников, наполненных светом Древа Духов. Сейн точно знает: $$$i$$$-й светильник горит в моменты времени с $$$l_i$$$ по $$$r_i$$$ включительно. Чтобы открыть дверь, необходимо выбрать такие $$$k$$$ светильников, что они все горят одновременно в какой-то момент времени.

Пока Сейн решает, какие же $$$k$$$ светильников выбрать, Ори стало интересно: а сколько всего существует способов выбрать $$$k$$$ светильников так, чтобы дверь открылась? Может получиться и так, что Сейн что-то напутал, и таких $$$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$$$.

Примеры
Входные данные
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
Примечание

В первом примере всего девять подходящих наборов из $$$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$$$, поэтому подходит каждый светильник.

В третьем примере нет двух светильников, горящих одновременно, поэтому ответ 0.

В четвертом примере все светильники горят в момент времени $$$3$$$, поэтому ответ 1.

В пятом примере всего семь наборов из $$$k$$$ ламп: $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(3, 4)$$$, $$$(3, 5)$$$, $$$(4, 5)$$$.