"Pretty Derby" is a racing simulation game. As a fanatical fan of the game, you need to perform well in the acceleration phase of a race to win the competition.

The following is a simplified model of the acceleration phase: at the beginning of the acceleration phase, your character needs to accelerate from $v_1$ to $v_2$. Your character has an initial acceleration $a_0$ and can further increase the acceleration through skills.

You have $n$ acceleration skills. The $i$-th skill provides an acceleration of $a_i$, lasts for $t_i$ units of time, and has a success probability of $p_i\%$. To simplify the problem, if a skill is successfully activated, it is considered to take effect immediately at the start of the acceleration phase. Furthermore, whether a skill is successfully activated is independent and random; that is, whether one of your skills is activated does not affect the success rate of another.

If the $i$-th skill is successfully activated, it will provide an additional acceleration of $a_i$ for the next $t_i$ units of time; otherwise, it has no effect. When the speed reaches $v_2$, the acceleration stops immediately, even if some skills are still within their duration. Additionally, to avoid excessive acceleration, you have set an upper limit on acceleration of $v_2 - v_1$. Therefore, the actual acceleration at any moment is: $\min(a_0 + \text{sum of accelerations of all successfully activated skills that are still within their duration}, v_2 - v_1)$.

Now you want to know, under the above rules, what is the expected acceleration time to accelerate from $v_1$ to $v_2$.

Input

The first line contains four positive integers $n, v_1, v_2, a_0$ ($1 \le n, v_1, v_2, a_0 \le 1000, v_1 < v_2$), representing the number of skills, the initial speed, the target speed, and the initial acceleration.

The next $n$ lines each contain three positive integers $a_i, t_i, p_i$ ($1 \le a_i, t_i \le 1000, 0 \le p_i \le 100$), representing the acceleration $a_i$, duration $t_i$, and success probability $p_i\%$ of the $i$-th skill.

Output

Output a single integer representing the expected acceleration time modulo $998244353$.

Formally, let $M = 998244353$. It can be proven that the exact answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not\equiv 0 \pmod M$. You need to output $p \cdot q^{-1} \pmod M$, which is the integer $x$ such that $0 \le x < M$ and $qx \equiv p \pmod M$. It can be proven that such an $x$ is unique.

Examples

Input 1

1 20 32 2
1 4 50

Output 1

5

Input 2

2 20 30 1
100 1 10
1 1 10

Output 2

828542822

Input 3

1 1 10 1
4 10 50

Output 3

199648876

Input 4

1 1 5 6
5 2 30

Output 4

1

Note

Explanation 1

There is a 50% probability that the skill is successfully activated, in which case it only takes 4 units of time to finish accelerating. There is a 50% probability that the skill is not successfully activated, in which case it takes 6 units of time to finish accelerating. Therefore, the expected acceleration time is $\frac{1}{2} \times 4 + \frac{1}{2} \times 6 = 5$.

Explanation 2

There is a 10% probability that the first skill is successfully activated, in which case the acceleration has already reached the limit, so it takes 1 unit of time to accelerate. There is a 9% probability that the second skill is successfully activated but the first one is not; the second skill can only last for 1 unit of time, so it takes 9 units of time to successfully accelerate. There is an 81% probability that neither skill is successfully activated, in which case it takes 10 units of time to accelerate. Therefore, the expected acceleration time is $\frac{901}{100}$. $100 \times 828542822 \equiv 901 \pmod{998244353}$, so the answer is 828542822.

Explanation 3

There is a 50% probability that the skill is successfully activated, in which case it only takes $\frac{9}{5}$ units of time to finish accelerating. There is a 50% probability that the skill is not successfully activated, in which case it takes 9 units of time to finish accelerating. Therefore, the expected acceleration time is $\frac{1}{2} \times \frac{9}{5} + \frac{1}{2} \times 9 = \frac{27}{5}$. $5 \times 199648876 \equiv 27 \pmod{998244353}$, so the answer is 199648876.