M. Pretty Derby

《Pretty Derby》 es un juego de carreras y entrenamiento. Como un fanático entusiasta de las "Pretty Derby", necesitas tener un desempeño excelente en la fase de aceleración de la carrera para poder ganar el gran premio.

A continuación se presenta un modelo simplificado de la fase de aceleración: al inicio de la fase de aceleración, tu personaje necesita aumentar su velocidad desde $v_1$ hasta $v_2$. Tu personaje tiene una aceleración inicial $a_0$ y puede mejorar su aceleración mediante habilidades.

Posees $n$ habilidades de aceleración. La $i$-ésima habilidad tiene una aceleración de $a_i$, una duración de $t_i$ unidades de tiempo y una probabilidad de activación exitosa de $p_i\%$. Para simplificar el problema, si una habilidad se activa con éxito, se considera que surte efecto inmediatamente al inicio de la fase de aceleración. Además, la activación exitosa de las habilidades es independiente y aleatoria, lo que significa que la activación de una habilidad no afecta la probabilidad de éxito de otra.

Si la $i$-ésima habilidad se activa con éxito, proporcionará una aceleración adicional de $a_i$ durante los siguientes $t_i$ unidades de tiempo; de lo contrario, no produce ningún efecto. Cuando la velocidad alcanza $v_2$, la aceleración se detiene inmediatamente, incluso si todavía hay habilidades en curso. Además, para evitar una aceleración excesiva, has establecido un límite superior de aceleración de $v_2 - v_1$. Por lo tanto, la aceleración real en cualquier momento es: $\min(a_0 + \text{suma de las aceleraciones de las habilidades activadas con éxito que aún están en curso}, v_2 - v_1)$.

Ahora deseas saber, bajo las reglas anteriores, cuál es el tiempo de aceleración esperado para pasar de $v_1$ a $v_2$.

Entrada

La primera línea contiene cuatro enteros positivos $n, v_1, v_2, a_0$ ($1 \le n, v_1, v_2, a_0 \le 1000, v_1 < v_2$), que representan la cantidad de habilidades, la velocidad inicial, la velocidad final y la aceleración inicial.

Las siguientes $n$ líneas contienen cada una tres enteros positivos $a_i, t_i, p_i$ ($1 \le a_i, t_i \le 1000, 0 \le p_i \le 100$), que representan que la aceleración de la $i$-ésima habilidad es $a_i$, su duración es $t_i$ unidades de tiempo y la probabilidad de activación exitosa es $p_i\%$.

Salida

Imprime un solo entero que represente el tiempo de aceleración esperado módulo $998244353$.

Formalmente, sea $M = 998244353$. Se puede demostrar que la respuesta exacta puede expresarse como una fracción irreducible $\frac{p}{q}$, donde $p$ y $q$ son enteros y $q \not\equiv 0 \pmod M$. Debes imprimir $p \cdot q^{-1} \pmod M$, es decir, el entero $x$ tal que $0 \le x < M$ y $qx \equiv p \pmod M$. Se puede demostrar que dicho $x$ es único.

Ejemplos

Entrada 1

1 20 32 2
1 4 50

Salida 1

5

Entrada 2

2 20 30 1
100 1 10
1 1 10

Salida 2

828542822

Entrada 3

1 1 10 1
4 10 50

Salida 3

199648876

Entrada 4

1 1 5 6
5 2 30

Salida 4

1

Nota

Explicación del Ejemplo 1

Existe un 50% de probabilidad de activar la habilidad con éxito, en cuyo caso solo se necesitan 4 unidades de tiempo para completar la aceleración. Existe un 50% de probabilidad de no activar la habilidad con éxito, en cuyo caso se necesitan 6 unidades de tiempo para completar la aceleración. Por lo tanto, el tiempo de aceleración esperado es $\frac{1}{2} \times 4 + \frac{1}{2} \times 6 = 5$.

Explicación del Ejemplo 2

Existe un 10% de probabilidad de activar la primera habilidad con éxito, en cuyo caso la aceleración ya ha alcanzado el límite, por lo que se necesita 1 unidad de tiempo para acelerar. Existe un 9% de probabilidad de activar la segunda habilidad con éxito pero no la primera; la segunda habilidad solo puede durar 1 unidad de tiempo, por lo que se necesitan 9 unidades de tiempo para completar la aceleración. Existe un 81% de probabilidad de que ninguna de las dos habilidades se active con éxito, en cuyo caso se necesitan 10 unidades de tiempo para acelerar. Por lo tanto, el tiempo de aceleración esperado es $\frac{901}{100}$. $100 \times 828542822 \equiv 901 \pmod{998244353}$, por lo que la respuesta es $828542822$.

Explicación del Ejemplo 3

Existe un 50% de probabilidad de activar la habilidad con éxito, en cuyo caso solo se necesitan $\frac{9}{5}$ unidades de tiempo para completar la aceleración. Existe un 50% de probabilidad de no activar la habilidad con éxito, en cuyo caso se necesitan 9 unidades de tiempo para completar la aceleración. Por lo tanto, el tiempo de aceleración esperado es $\frac{1}{2} \times \frac{9}{5} + \frac{1}{2} \times 9 = \frac{27}{5}$. $5 \times 199648876 \equiv 27 \pmod{998244353}$, por lo que la respuesta es $199648876$.