Codeforces Round 672 (Div. 2) |
---|
Закончено |
Преодолев множество сложных испытаний, Ори и Сейн наконец-то зажгли Укрытый Светильник и нашли Печать Гумон, ключ к Руинам Форлорна! Когда же они наконец вставили Печать в дверь... ничего не произошло.
Ори очень этому удивился, но Сейн быстро все объяснил: хитрые Гумон решили наложить дополнительную защиту на дверь.
На двери расположено $$$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)$$$.
Название |
---|