D. Покрытие отрезками
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть полоска, разделенная на $$$m$$$ ячеек, которые пронумерованы от $$$1$$$ до $$$m$$$ слева направо.

Вам даны $$$n$$$ отрезков. Каждый отрезок описывается четырьмя числами: $$$l$$$, $$$r$$$, $$$p$$$ и $$$q$$$ — отрезок покрывает ячейки от $$$l$$$ до $$$r$$$ включительно и существует с вероятностью $$$\frac{p}{q}$$$ (независимо).

Ваша задача — посчитать вероятность того, что каждая из ячеек покрыта ровно одним отрезком.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$).

Затем следуют $$$n$$$ строк. $$$i$$$-я из них содержит четыре целых числа $$$l_i$$$, $$$r_i$$$, $$$p_i$$$ и $$$q_i$$$ ($$$1 \le l_i \le r_i \le m$$$; $$$1 \le p_i \lt q_i \lt 998244353$$$).

Выходные данные

Выведите одно целое число — вероятность того, что каждая из ячеек покрыта ровно одним отрезком, взятая по модулю $$$998244353$$$.

Формально, вероятность может быть выражена как несократимая дробь $$$\frac{x}{y}$$$. Вам нужно вывести значение $$$x \cdot y^{-1} \bmod 998244353$$$, где $$$y^{-1}$$$ — это целое число, такое что $$$y \cdot y^{-1} \bmod 998244353 = 1$$$.

Примеры
Входные данные
3 3
1 2 1 3
3 3 1 2
1 3 2 3
Выходные данные
610038216
Входные данные
2 3
1 2 1 2
2 3 1 2
Выходные данные
0
Входные данные
8 5
1 3 1 2
1 5 1 6
1 4 4 5
5 5 1 7
4 5 1 2
4 5 2 5
3 3 2 7
1 2 1 3
Выходные данные
94391813
Примечание

В первом примере вероятность равна $$$\frac{5}{18}$$$.