M. Nữ thần đua ngựa (Pretty Derby)

"Pretty Derby" là một trò chơi mô phỏng đua ngựa. Là một người hâm mộ cuồng nhiệt của các nữ thần đua ngựa, bạn cần phải thể hiện xuất sắc trong giai đoạn tăng tốc của cuộc đua để giành chiến thắng.

Dưới đây là một mô hình đơn giản hóa của giai đoạn tăng tốc: khi bắt đầu giai đoạn tăng tốc, nhân vật của bạn cần tăng tốc từ $v_1$ lên $v_2$. Nhân vật của bạn có gia tốc ban đầu là $a_0$ và có thể sử dụng các kỹ năng để tăng thêm gia tốc.

Bạn có $n$ kỹ năng tăng tốc, kỹ năng thứ $i$ có gia tốc là $a_i$, thời gian duy trì là $t_i$ đơn vị thời gian, và xác suất kích hoạt thành công là $p_i\%$. Để đơn giản hóa vấn đề, nếu một kỹ năng được kích hoạt thành công, nó được coi là có hiệu lực ngay lập tức khi bắt đầu giai đoạn tăng tốc. Ngoài ra, việc kích hoạt thành công các kỹ năng là các sự kiện độc lập ngẫu nhiên, nghĩa là việc một kỹ năng của bạn có được kích hoạt hay không sẽ không ảnh hưởng đến xác suất thành công của kỹ năng khác.

Nếu kỹ năng thứ $i$ được kích hoạt thành công, nó sẽ cung cấp thêm gia tốc $a_i$ trong $t_i$ đơn vị thời gian tiếp theo; nếu không, nó không tạo ra bất kỳ ảnh hưởng nào. Khi tốc độ đạt đến $v_2$, ngay cả khi vẫn còn kỹ năng đang trong thời gian duy trì, quá trình tăng tốc sẽ dừng lại ngay lập tức. Ngoài ra, để tránh gia tốc quá lớn, bạn quy định giới hạn trên của gia tốc là $v_2 - v_1$. Do đó, gia tốc thực tế tại bất kỳ thời điểm nào là: $\min(a_0 + \text{tổng gia tốc của các kỹ năng kích hoạt thành công và vẫn còn trong thời gian duy trì}, v_2 - v_1)$.

Bây giờ bạn muốn biết, theo các quy tắc trên, thời gian tăng tốc kỳ vọng từ $v_1$ đến $v_2$ là bao nhiêu.

Dữ liệu vào

Dòng đầu tiên gồm bốn số nguyên dương $n, v_1, v_2, a_0$ ($1 \le n, v_1, v_2, a_0 \le 1000, v_1 < v_2$), biểu thị số lượng kỹ năng, tốc độ ban đầu, tốc độ kết thúc và gia tốc ban đầu.

$n$ dòng tiếp theo, mỗi dòng gồm ba số nguyên dương $a_i, t_i, p_i$ ($1 \le a_i, t_i \le 1000, 0 \le p_i \le 100$) biểu thị gia tốc của kỹ năng thứ $i$ là $a_i$, thời gian duy trì là $t_i$ đơn vị thời gian, và xác suất kích hoạt thành công là $p_i\%$.

Dữ liệu ra

In ra một số nguyên duy nhất, biểu thị kết quả của thời gian tăng tốc kỳ vọng lấy mô-đun $998244353$.

Cụ thể, đặt $M = 998244353$, có thể chứng minh rằng đáp án chính xác có thể được biểu diễn dưới dạng phân số tối giản $\frac{p}{q}$, trong đó $p$ và $q$ là các số nguyên và $q \not\equiv 0 \pmod M$. Bạn cần xuất ra $p \cdot q^{-1} \pmod M$, tức là xuất ra số nguyên $x$ thỏa mãn $0 \le x < M$ và $qx \equiv p \pmod M$. Có thể chứng minh rằng $x$ thỏa mãn điều kiện là duy nhất.

Ví dụ

Ví dụ 1

1 20 32 2
1 4 50

Ví dụ 1 (Kết quả)

5

Ví dụ 2

2 20 30 1
100 1 10
1 1 10

Ví dụ 2 (Kết quả)

828542822

Ví dụ 3

1 1 10 1
4 10 50

Ví dụ 3 (Kết quả)

199648876

Ví dụ 4

1 1 5 6
5 2 30

Ví dụ 4 (Kết quả)

1

Ghi chú

Giải thích Ví dụ 1

Có 50% xác suất kích hoạt thành công kỹ năng, khi đó chỉ cần 4 đơn vị thời gian để tăng tốc xong. Có 50% xác suất không kích hoạt thành công kỹ năng, khi đó cần 6 đơn vị thời gian để tăng tốc xong, do đó thời gian tăng tốc kỳ vọng là $\frac{1}{2} \times 4 + \frac{1}{2} \times 6 = 5$.

Giải thích Ví dụ 2

Có 10% xác suất kích hoạt thành công kỹ năng thứ nhất, lúc này gia tốc đã đạt giới hạn, do đó cần 1 đơn vị thời gian để tăng tốc. Có 9% xác suất kích hoạt thành công kỹ năng thứ hai nhưng không kích hoạt thành công kỹ năng thứ nhất, kỹ năng thứ hai chỉ có thể duy trì trong 1 đơn vị thời gian, do đó cần 9 đơn vị thời gian để tăng tốc thành công. Có 81% xác suất cả hai kỹ năng đều không kích hoạt thành công, lúc này cần 10 đơn vị thời gian để tăng tốc. Do đó thời gian tăng tốc kỳ vọng là $\frac{901}{100}$. $100 \times 828542822 \equiv 901 \pmod{998244353}$, vì vậy đáp án là 828542822.

Giải thích Ví dụ 3

Có 50% xác suất kích hoạt thành công kỹ năng, lúc này chỉ cần $\frac{9}{5}$ đơn vị thời gian để tăng tốc xong. Có 50% xác suất không kích hoạt thành công kỹ năng, lúc này cần 9 đơn vị thời gian để tăng tốc xong, do đó thời gian tăng tốc kỳ vọng là $\frac{1}{2} \times \frac{9}{5} + \frac{1}{2} \times 9 = \frac{27}{5}$. $5 \times 199648876 \equiv 27 \pmod{998244353}$, vì vậy đáp án là 199648876.