M. Девушка-лошадь

«Pretty Derby» — это игра про тренировку скаковых лошадей. Как заядлый любитель этой игры, вы должны показать отличные результаты на этапе ускорения, чтобы выиграть соревнование.

Ниже представлена упрощенная модель этапа ускорения: в начале этапа ускорения ваш персонаж должен увеличить скорость с $v_1$ до $v_2$. У вашего персонажа есть начальное ускорение $a_0$, и он может использовать навыки для дальнейшего увеличения ускорения.

У вас есть $n$ навыков ускорения. Для $i$-го навыка ускорение составляет $a_i$, длительность действия — $t_i$ единиц времени, а вероятность успешного применения — $p_i\%$. Для упрощения задачи будем считать, что если навык успешно применен, он вступает в силу немедленно в начале этапа ускорения. Кроме того, успешность применения навыков является независимой случайной величиной, то есть применение одного навыка не влияет на вероятность успеха другого.

Если $i$-й навык успешно применен, он обеспечивает дополнительное ускорение $a_i$ в течение следующих $t_i$ единиц времени; в противном случае он не оказывает никакого влияния. Когда скорость достигает $v_2$, ускорение немедленно прекращается, даже если некоторые навыки все еще действуют. Кроме того, чтобы избежать чрезмерного ускорения, вы установили верхний предел ускорения, равный $v_2 - v_1$. Таким образом, фактическое ускорение в любой момент времени равно: $\min(a_0 + \text{сумма ускорений всех успешно примененных навыков, действие которых еще не закончилось}, v_2 - v_1)$.

Теперь вы хотите узнать, каково ожидаемое время ускорения от $v_1$ до $v_2$ при соблюдении вышеуказанных правил.

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

Первая строка содержит четыре целых положительных числа $n, v_1, v_2, a_0$ ($1 \le n, v_1, v_2, a_0 \le 1000, v_1 < v_2$), обозначающих количество навыков, начальную скорость, конечную скорость и начальное ускорение соответственно.

Следующие $n$ строк содержат по три целых положительных числа $a_i, t_i, p_i$ ($1 \le a_i, t_i \le 1000, 0 \le p_i \le 100$), где $a_i$ — ускорение $i$-го навыка, $t_i$ — длительность его действия, а $p_i\%$ — вероятность успешного применения.

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

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

Формально, пусть $M = 998244353$. Можно доказать, что точный ответ можно представить в виде несократимой дроби $\frac{p}{q}$, где $p$ и $q$ — целые числа и $q \not\equiv 0 \pmod M$. Вам нужно вывести $p \cdot q^{-1} \pmod M$, то есть такое целое число $x$, что $0 \le x < M$ и $qx \equiv p \pmod M$. Можно доказать, что такое $x$ единственно.

Примеры

Пример 1

1 20 32 2
1 4 50

5

Пример 2

2 20 30 1
100 1 10
1 1 10

828542822

Пример 3

1 1 10 1
4 10 50

199648876

Пример 4

1 1 5 6
5 2 30

1

Примечание

Пояснение к примеру 1

С вероятностью 50% навык успешно применяется, тогда для завершения ускорения требуется 4 единицы времени. С вероятностью 50% навык не применяется, тогда требуется 6 единиц времени. Таким образом, ожидаемое время ускорения составляет $\frac{1}{2} \times 4 + \frac{1}{2} \times 6 = 5$.

Пояснение к примеру 2

С вероятностью 10% успешно применяется первый навык, при этом ускорение достигает предела, поэтому требуется 1 единица времени. С вероятностью 9% успешно применяется второй навык, но не первый; второй навык действует только 1 единицу времени, поэтому требуется 9 единиц времени для завершения ускорения. С вероятностью 81% ни один из навыков не применяется, тогда требуется 10 единиц времени. Ожидаемое время ускорения составляет $\frac{901}{100}$. $100 \times 828542822 \equiv 901 \pmod{998244353}$, поэтому ответ — 828542822.

Пояснение к примеру 3

С вероятностью 50% навык успешно применяется, тогда требуется $\frac{9}{5}$ единиц времени. С вероятностью 50% навык не применяется, тогда требуется 9 единиц времени. Ожидаемое время ускорения составляет $\frac{1}{2} \times \frac{9}{5} + \frac{1}{2} \times 9 = \frac{27}{5}$. $5 \times 199648876 \equiv 27 \pmod{998244353}$, поэтому ответ — 199648876.