M. 賽馬娘

『ウマ娘 プリティーダービー』は競走育成ゲームである。熱狂的なウマ娘ファンであるあなたは、レースの加速段階で優れたパフォーマンスを発揮し、大会で優勝しなければならない。

以下は加速段階の簡略化されたモデルである。加速段階の開始時、あなたのキャラクターは速度を $v_1$ から $v_2$ まで加速させる必要がある。キャラクターは初期加速度 $a_0$ を持ち、スキルを使用して加速度をさらに高めることができる。

あなたは $n$ 個の加速スキルを所有しており、第 $i$ 番目のスキルの加速度は $a_i$、持続時間は $t_i$ 単位時間、成功確率は $p_i\%$ である。問題を簡略化するため、あるスキルが成功した場合、それは加速段階の開始時に即座に有効になるとみなす。また、スキルの成功は独立した確率事象であり、あるスキルの発動が他のスキルの成功率に影響を与えることはない。

第 $i$ 番目のスキルが成功した場合、その後の $t_i$ 単位時間の間、追加で $a_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$ $a_1 \ t_1 \ p_1$ $a_2 \ t_2 \ p_2$ $\vdots$ $a_n \ t_n \ p_n$

1 行目に 4 つの正整数 $n, v_1, v_2, a_0$ ($1 \le n, v_1, v_2, a_0 \le 1000, v_1 < v_2$) が与えられ、それぞれスキルの数、初速度、終速度、初期加速度を表す。

続く $n$ 行の各行には、3 つの正整数 $a_i, t_i, p_i$ ($1 \le a_i, t_i \le 1000, 0 \le p_i \le 100$) が与えられ、それぞれ第 $i$ 番目のスキルの加速度、持続時間、成功確率（パーセント）を表す。

出力

期待される加速時間を $998244353$ で割った余りを出力せよ。

形式的には、$M = 998244353$ とすると、正確な答えは既約分数 $\frac{p}{q}$ として表すことができ、ここで $p, q$ は整数であり $q \not\equiv 0 \pmod M$ である。出力すべき値は $p \cdot q^{-1} \pmod M$ であり、これは $0 \le x < M$ かつ $qx \equiv p \pmod M$ を満たす整数 $x$ である。条件を満たす $x$ は一意に定まることが証明できる。

入出力例

入力 1

1 20 32 2
1 4 50

出力 1

5

入力 2

2 20 30 1
100 1 10
1 1 10

出力 2

828542822

入力 3

1 1 10 1
4 10 50

出力 3

199648876

入力 4

1 1 5 6
5 2 30

出力 4

1

注記

入出力例 1 の解説

50% の確率でスキルが成功し、その場合 4 単位時間で加速が完了する。50% の確率でスキルが失敗し、その場合 6 単位時間で加速が完了する。したがって、期待される加速時間は $\frac{1}{2} \times 4 + \frac{1}{2} \times 6 = 5$ となる。

入出力例 2 の解説

10% の確率で最初のスキルが成功し、このとき加速度はすでに上限に達しているため、1 単位時間で加速が完了する。9% の確率で 2 番目のスキルが成功するが最初のスキルは失敗し、2 番目のスキルは 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$ となる。