M. Fille-Cheval
« Uma Musume Pretty Derby » est un jeu de simulation de course. En tant que fan passionné de filles-chevaux, vous devez exceller dans la phase d'accélération pour remporter la course.
Voici un modèle simplifié de la phase d'accélération : au début de cette phase, votre personnage doit accélérer d'une vitesse $v_1$ à une vitesse $v_2$. Votre personnage possède une accélération initiale $a_0$ et peut utiliser des compétences pour augmenter davantage son accélération.
Vous disposez de $n$ compétences d'accélération. La $i$-ième compétence fournit une accélération de $a_i$, dure $t_i$ unités de temps, et a une probabilité de succès de $p_i\%$. Pour simplifier le problème, si une compétence est activée avec succès, elle est considérée comme prenant effet immédiatement au début de la phase d'accélération. De plus, le succès de l'activation d'une compétence est un événement aléatoire indépendant, ce qui signifie que l'activation réussie d'une compétence n'affecte pas la probabilité de succès d'une autre.
Si la $i$-ième compétence est activée avec succès, elle fournit une accélération supplémentaire de $a_i$ pendant les $t_i$ unités de temps suivantes ; sinon, elle n'a aucun effet. Lorsque la vitesse atteint $v_2$, l'accélération s'arrête immédiatement, même si certaines compétences sont encore actives. De plus, pour éviter une accélération excessive, vous avez fixé une limite supérieure d'accélération à $v_2 - v_1$. Par conséquent, l'accélération réelle à tout instant est : $\min(a_0 + \text{somme des accélérations des compétences activées avec succès et encore actives}, v_2 - v_1)$.
Vous souhaitez maintenant connaître, selon ces règles, l'espérance du temps d'accélération pour passer de $v_1$ à $v_2$.
Entrée
La première ligne contient quatre entiers positifs $n, v_1, v_2, a_0$ ($1 \le n, v_1, v_2, a_0 \le 1000, v_1 < v_2$), représentant le nombre de compétences, la vitesse initiale, la vitesse finale et l'accélération initiale.
Les $n$ lignes suivantes contiennent chacune trois entiers positifs $a_i, t_i, p_i$ ($1 \le a_i, t_i \le 1000, 0 \le p_i \le 100$), représentant l'accélération, la durée et la probabilité de succès en pourcentage de la $i$-ième compétence.
Sortie
Affichez un seul entier représentant l'espérance du temps d'accélération modulo $998244353$.
Formellement, soit $M = 998244353$. On peut prouver que la réponse exacte peut être exprimée sous la forme d'une fraction irréductible $\frac{p}{q}$, où $p$ et $q$ sont des entiers et $q \not\equiv 0 \pmod M$. Vous devez afficher $p \cdot q^{-1} \pmod M$, c'est-à-dire l'entier $x$ tel que $0 \le x < M$ et $qx \equiv p \pmod M$. On peut prouver qu'un tel $x$ est unique.
Exemples
Entrée 1
1 20 32 2 1 4 50
Sortie 1
5
Entrée 2
2 20 30 1 100 1 10 1 1 10
Sortie 2
828542822
Entrée 3
1 1 10 1 4 10 50
Sortie 3
199648876
Entrée 4
1 1 5 6 5 2 30
Sortie 4
1
Remarque
Explication de l'exemple 1
Il y a 50 % de chances que la compétence soit activée avec succès, auquel cas il ne faut que 4 unités de temps pour terminer l'accélération. Il y a 50 % de chances que la compétence ne soit pas activée, auquel cas il faut 6 unités de temps pour terminer l'accélération. L'espérance du temps d'accélération est donc $\frac{1}{2} \times 4 + \frac{1}{2} \times 6 = 5$.
Explication de l'exemple 2
Il y a 10 % de chances que la première compétence soit activée avec succès, auquel cas l'accélération a déjà atteint la limite, nécessitant 1 unité de temps. Il y a 9 % de chances que la deuxième compétence soit activée avec succès mais pas la première ; la deuxième compétence ne peut durer qu'une unité de temps, nécessitant donc 9 unités de temps pour terminer l'accélération. Il y a 81 % de chances qu'aucune des deux compétences ne soit activée, nécessitant 10 unités de temps. L'espérance du temps d'accélération est donc $\frac{901}{100}$. $100 \times 828542822 \equiv 901 \pmod{998244353}$, la réponse est donc $828542822$.
Explication de l'exemple 3
Il y a 50 % de chances que la compétence soit activée avec succès, auquel cas il ne faut que $\frac{9}{5}$ unités de temps pour terminer l'accélération. Il y a 50 % de chances que la compétence ne soit pas activée, auquel cas il faut 9 unités de temps pour terminer l'accélération. L'espérance du temps d'accélération est donc $\frac{1}{2} \times \frac{9}{5} + \frac{1}{2} \times 9 = \frac{27}{5}$. $5 \times 199648876 \equiv 27 \pmod{998244353}$, la réponse est donc $199648876$.