《우마무스메 프리티 더비(Pretty Derby)》는 경주 육성 게임입니다. 열렬한 우마무스메 애호가로서, 당신은 경주의 가속 구간에서 뛰어난 성적을 거두어야 대회에서 우승할 수 있습니다.

다음은 가속 구간에 대한 간략화된 모델입니다. 가속 구간이 시작될 때, 당신의 캐릭터는 속도를 $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$ ($1 \le n, v_1, v_2, a_0 \le 1000, v_1 < v_2$)가 주어지며, 각각 스킬의 개수, 초기 속도, 종료 속도, 초기 가속도를 나타냅니다.

다음 $n$개의 줄에는 각각 세 개의 정수 $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%의 확률로 두 번째 스킬은 성공하지만 첫 번째 스킬은 실패하며, 두 번째 스킬은 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입니다.