P9621 See You Next Time

> In the season that has passed, the lost treasure. > > Is a precious jigsaw puzzle missing one corner. > > Just like how white snow gently piles up on the streets. > > Let it also fill all the blank spaces in the memory album.

There is a piece of music made up of $n$ circles. The player will **uniformly randomly choose** a starting position from $1 \sim n$, then click that position and all circles after it in order to finish playing the piece. For each circle, the click accuracy has four possible judgments: $\texttt{GREAT,OK,MEH,MISS}$. There is a mechanism: after $K$ consecutive $\texttt{MISS}$ judgments, the player will be forced to exit the game; otherwise, the player will keep playing until all circles have been clicked. Now you are given, for each circle, the probability that the player gets each judgment. For the $i$-th circle, the probabilities of $\texttt{GREAT}$, $\texttt{OK}$, $\texttt{MEH}$, and $\texttt{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 whole performance. It is computed as follows: suppose in the whole performance there are $a$ times $\texttt{GREAT}$, $b$ times $\texttt{OK}$, $c$ times $\texttt{MEH}$, and $d$ times $\texttt{MISS}$, then the score is $300a+100b+50c$. You need to answer the expected value of the player's score. Note: If the player is forced to exit the game, then when computing the score, the whole performance includes all clicks from the starting click up to and including the click that produced the last $\texttt{MISS}$ judgment. For some test points with larger data sizes, in order to reduce the amount of input/output interaction, we use a different input method. You need to include the data generator provided in the attached file in 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.

The first line contains two integers $Type,seed$. When $Type=1$, after reading $seed$ you need to call `Ge.init(seed)` to set the seed of the data generator. Otherwise, you may ignore $seed$. The second line contains two integers $n,K$. Then there are two cases: - $Type=0$. The next $n$ lines each contain $4$ integers, representing $P_{i,0}\ P_{i,1}\ P_{i,2}\ P_{i,3}$. - $Type=1$. There is no further input. After your $i$-th call to ``Ge.get(a,b,c,d)``, the values of $a,b,c,d$ are $P_{i,0}\ P_{i,1}\ P_{i,2}\ P_{i,3}$, respectively.

Output one integer per line, representing the answer $\bmod\ 998244353$. Note: It can be proven that the answer can be expressed as $p/q$. You need to output the result of multiplying $p$ by the modular inverse of $q$ modulo $998244353$, and then taking it modulo $998244353$.

|Test Point ID|Constraints|Special Property| |:-:|:-:|:-:| |$1\sim 2$|$n\le 5$|| |$3\sim 4$|$n\le 50$|| |$5\sim 6$|$n\le 10^3$|| |$7\sim 8$|$n\le 10^5,K\le 10^3$|| |$9\sim 10$||$A$| |$11\sim 12$||$B$| |$13\sim 15$|$n,K\le 5\times 10^5$|| |$16\sim 20$|| $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}$ equals $0$ or equals $100$. --- For test points $1\sim 15$, $Type=0$; for test points $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$. Translated by ChatGPT 5