M. Pretty Derby

„Pretty Derby” to gra wyścigowa typu symulator. Jako zagorzały fan Pretty Derby musisz wykazać się w fazie przyspieszania, aby wygrać zawody.

Oto uproszczony model fazy przyspieszania: na początku fazy przyspieszania Twoja postać musi zwiększyć prędkość z $v_1$ do $v_2$. Twoja postać posiada początkowe przyspieszenie $a_0$ i może korzystać z umiejętności, aby je dodatkowo zwiększyć.

Posiadasz $n$ umiejętności przyspieszających. Dla $i$-tej umiejętności przyspieszenie wynosi $a_i$, czas trwania to $t_i$ jednostek czasu, a prawdopodobieństwo udanego użycia wynosi $p_i\%$. Dla uproszczenia przyjmijmy, że jeśli umiejętność zostanie pomyślnie użyta, zaczyna działać natychmiast na początku fazy przyspieszania. Ponadto, powodzenie użycia każdej umiejętności jest zdarzeniem niezależnym, co oznacza, że użycie jednej umiejętności nie wpływa na prawdopodobieństwo sukcesu innej.

Jeśli $i$-ta umiejętność zostanie pomyślnie użyta, zapewnia dodatkowe przyspieszenie $a_i$ przez następne $t_i$ jednostek czasu; w przeciwnym razie nie ma żadnego wpływu. Gdy prędkość osiągnie $v_2$, przyspieszanie zostaje natychmiast zatrzymane, nawet jeśli niektóre umiejętności są nadal aktywne.

Ponadto, aby uniknąć zbyt dużego przyspieszenia, ustalono górny limit przyspieszenia na poziomie $v_2 - v_1$. W związku z tym rzeczywiste przyspieszenie w dowolnym momencie wynosi: $\min(a_0 + \text{suma przyspieszeń wszystkich pomyślnie użytych i aktywnych umiejętności}, v_2 - v_1)$.

Oblicz oczekiwany czas przyspieszania z $v_1$ do $v_2$ zgodnie z powyższymi zasadami.

Wejście

Pierwsza linia zawiera cztery liczby całkowite $n, v_1, v_2, a_0$ ($1 \le n, v_1, v_2, a_0 \le 1000, v_1 < v_2$), oznaczające liczbę umiejętności, prędkość początkową, prędkość końcową oraz początkowe przyspieszenie.

Następnie $n$ linii, każda zawiera trzy liczby całkowite $a_i, t_i, p_i$ ($1 \le a_i, t_i \le 1000, 0 \le p_i \le 100$), oznaczające przyspieszenie $i$-tej umiejętności, czas jej trwania oraz prawdopodobieństwo sukcesu w procentach.

Wyjście

Wypisz jedną liczbę całkowitą oznaczającą oczekiwany czas przyspieszania modulo $998244353$.

Formalnie, niech $M = 998244353$. Można udowodnić, że dokładny wynik można przedstawić jako ułamek nieskracalny $\frac{p}{q}$, gdzie $p$ i $q$ są liczbami całkowitymi oraz $q \not\equiv 0 \pmod M$. Należy wypisać $p \cdot q^{-1} \pmod M$, czyli taką liczbę całkowitą $x$, że $0 \le x < M$ oraz $qx \equiv p \pmod M$. Można udowodnić, że takie $x$ jest unikalne.

Przykład

Wejście 1

1 20 32 2
1 4 50

Wyjście 1

5

Wejście 2

2 20 30 1
100 1 10
1 1 10

Wyjście 2

828542822

Wejście 3

1 1 10 1
4 10 50

Wyjście 3

199648876

Wejście 4

1 1 5 6
5 2 30

Wyjście 4

1

Uwagi

Wyjaśnienie 1

Istnieje $50\%$ szans na pomyślne użycie umiejętności, wtedy potrzeba $4$ jednostek czasu na zakończenie przyspieszania. Istnieje $50\%$ szans na niepowodzenie, wtedy potrzeba $6$ jednostek czasu. Oczekiwany czas wynosi $\frac{1}{2} \times 4 + \frac{1}{2} \times 6 = 5$.

Wyjaśnienie 2

Istnieje $10\%$ szans na pomyślne użycie pierwszej umiejętności, wtedy przyspieszenie osiąga limit i potrzeba $1$ jednostki czasu. Istnieje $9\%$ szans na pomyślne użycie drugiej umiejętności przy niepowodzeniu pierwszej; druga umiejętność trwa $1$ jednostkę czasu, więc potrzeba $9$ jednostek czasu. Istnieje $81\%$ szans, że żadna umiejętność nie zadziała, wtedy potrzeba $10$ jednostek czasu. Oczekiwany czas wynosi $\frac{901}{100}$. $100 \times 828542822 \equiv 901 \pmod{998244353}$, więc odpowiedzią jest $828542822$.

Wyjaśnienie 3

Istnieje $50\%$ szans na pomyślne użycie umiejętności, wtedy potrzeba $\frac{9}{5}$ jednostki czasu. Istnieje $50\%$ szans na niepowodzenie, wtedy potrzeba $9$ jednostek czasu. Oczekiwany czas wynosi $\frac{1}{2} \times \frac{9}{5} + \frac{1}{2} \times 9 = \frac{27}{5}$. $5 \times 199648876 \equiv 27 \pmod{998244353}$, więc odpowiedzią jest $199648876$.