Problem Background

In the seasons that have passed, the lost treasure

Is the precious puzzle piece missing a corner

Like the gentle accumulation of snow on the streets

It will also fill the blank pages of the memory album

Problem Description

There is a song composed of $n$ circles. Players will randomly and equally likely choose a position from $1$ to $n$ to start playing, sequentially clicking that position and all subsequent circles to complete the song.

There are four judgments for the accuracy of each circle click: $\texttt{GREAT, OK, MEH, MISS}$.

There is a mechanism: when there are $K$ consecutive $\texttt{MISS}$ judgments, the player will be forced to exit the game; otherwise, the player will continue playing until all circles are clicked.

Given the probabilities for each circle to achieve each judgment: for the $i$-th circle, the probabilities for judgments $\texttt{GREAT, OK, MEH, MISS}$ are $P_{i,0}/100, P_{i,1}/100, P_{i,2}/100, P_{i,3}/100$ respectively. It is guaranteed that $P_{i,0} + P_{i,1} + P_{i,2} + P_{i,3} = 100$.

The score is a measure of the entire performance. Its calculation method is as follows: suppose there are $a$ $\texttt{GREAT}$ judgments, $b$ $\texttt{OK}$ judgments, $c$ $\texttt{MEH}$ judgments, and $d$ $\texttt{MISS}$ judgments in the entire performance, then the score is $300a + 100b + 50c$.

You need to answer the expected score of the player.

Note: If the player is forced to exit the game, the score calculation includes all clicks from the start to the last $\texttt{MISS}$ judgment.

For test cases with large data ranges, to reduce the amount of input and output interaction, we have adopted a different input method. You need to add the data generator provided in the problem attachment to your C++ code. It is recommended to browse the function names provided in the generator before reading the following content, as this can help you better understand the input format.

Input Format

The first line contains two integers $Type, seed$.

When $Type = 1$, you need to call Ge.init(seed) after reading $seed$ to set the seed for the data generator. Otherwise, you can ignore $seed$.

The second line includes two integers $n, K$.

There are two cases:

• $Type = 0$. The next $n$ lines, each containing $4$ integers, represent $P_{i,0} P_{i,1} P_{i,2} P_{i,3}$.

• $Type = 1$. There is no further input. Each time you call Ge.get(a, b, c, d), the values of $a, b, c, d$ will be $P_{i,0} P_{i,1} P_{i,2} P_{i,3}$.

Output Format

One line containing an integer, representing the answer $\bmod\ 998244353$.

Note: It can be proven that the answer can be expressed as $p/q$. You need to output the product of $p$ and the modular inverse of $q$ under $\bmod\ 998244353$, modulo $998244353$.

Sample Input and Output

Sample Input #1

0 0
4 2
10 20 20 50
20 10 20 50
20 20 10 50
20 50 10 20

Sample Output #1

530317523

Sample Input #2

0 280114129
5 5
36 23 30 11
0 52 25 23
14 61 23 2
10 41 37 12
0 12 78 10

Sample Output #2

898420164

Sample Input #3

1 114
5141 919

Sample Output #3

800181066

Notes/Hints

$A$: It is guaranteed that $P_{i,3}$ is the same for all positions.

$B$: It is guaranteed that for all positions, $P_{i,3}$ is either $0$ or $100$.

For test cases numbered $1 \sim 15$, $Type = 0$; for test cases numbered $16 \sim 20$, $Type = 1$.

It is guaranteed that for all data, $0 \le P_{i,0/1/2/3} \le 100$, $1 \le K \le n \le 5 \times 10^6$, $Type = 0/1$, $1 \le seed \le 10^9$.

见题面 Input 部分

见题面 Output 部分