Преодолев множество сложных испытаний, Ори и Сейн наконец-то зажгли Укрытый Светильник и нашли Печать Гумон, ключ к Руинам Форлорна! Когда же они наконец вставили Печать в дверь... ничего не произошло.
Ори очень этому удивился, но Сейн быстро все объяснил: хитрые Гумон решили наложить дополнительную защиту на дверь.
На двери расположено \(n\) светильников, наполненных светом Древа Духов. Сейн точно знает: \(i\)-й светильник горит в моменты времени с \(l_i\) по \(r_i\) включительно. Чтобы открыть дверь, необходимо выбрать такие \(k\) светильников, что они все горят одновременно в какой-то момент времени.
Пока Сейн решает, какие же \(k\) светильников выбрать, Ори стало интересно: а сколько всего существует способов выбрать \(k\) светильников так, чтобы дверь открылась? Может получиться и так, что Сейн что-то напутал, и таких \(k\) светильников просто не существует. Так как это число может быть очень большим, выводите его остаток от деления на \(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\), поэтому подходит каждый светильник.
В третьем примере нет двух светильников, горящих одновременно, поэтому ответ 0.
В четвертом примере все светильники горят в момент времени \(3\), поэтому ответ 1.
В пятом примере всего семь наборов из \(k\) ламп: \((1, 2)\), \((1, 3)\), \((2, 3)\), \((2, 4)\), \((3, 4)\), \((3, 5)\), \((4, 5)\).