U517306 「ALFR Round 3」D Nuclear Fission

[Chinese Statement](P11448). EmptyAlien is studying for the Physics Olympiad.

There are $n$ radioactive atoms that will undergo fission reactions for $k$ seconds. If at the beginning of the $t$-th second, atom $i$ is bombarded by $b\ (b>0)$ neutrons, it will release $a_i + b$ units of energy during the $t$-th second and will release $1$ neutron to each of the atoms numbered $x_{i,1}, x_{i,2}, \ldots, x_{i,a_i}$. Thus, at the beginning of the next second ($t+1$), the number of neutrons hitting each of $x_{i,1}, x_{i,2}, \dots, x_{i,a_i}$ will increase by $1$ (**if $t=k$, meaning this is the last second, then neutrons will not be released by bombarded atoms**). If an atom is not bombarded by any neutrons at the beginning of a second, it will not release energy or neutrons. At the beginning of each second, atoms numbered $v_1, v_2, \ldots, v_m$ are bombarded by $1$ neutron. Therefore, from the beginning of the first second until the end of the $k$-th second, how much energy will each atom release? **Output the answer modulo $998244353$.**

无

无

Explanation of sample #1: - In the first second, atom $1$ is hit by $1$ neutron, releasing $1$ neutron to atom $2$, thus releasing $2$ units of energy. - In the second second, atom $1$ is hit by $1$ neutron, releasing $1$ neutron to atom $2$, and releasing $2$ units of energy. Simultaneously, atom $2$ is hit by $1$ neutron, releasing $1$ neutron to atom $3$, and releasing $2$ units of energy. - In the third second, atom $1$ is hit by $1$ neutron, releasing $2$ units of energy. Meanwhile, atom $2$ is hit by $1$ neutron, releasing $2$ units of energy, and atom $3$ is hit by $1$ neutron, releasing $2$ units of energy. Thus, atom $1$ releases a total of $6$ units of energy, atom $2$ releases $4$ units of energy, and atom $3$ releases $2$ units of energy. | Subtask | Score | Constraints | | :----------: | :----------: | :----------: | | $0$ | $5$ | $m=n,v_i=i,a_i=1,x_{i,1}=1$ | | $1$ | $10$ | $m=1,v_1=1,a_i=1,x_{i,1}=(i \bmod n)+1$ | | $2$ | $20$ | $n,\sum a_i \leq 10^3$, $1 \leq k \leq 10^6$ | | $3$ | $30$ | $1 \leq k \leq 10^6$ | | $4$ | $35$ | - | For all the tests, $1\le n,\sum a_i\le5\times10^5$, $1 \leq k \leq 10^{18}$, $0 \leq a_i \leq 5 \times 10^5$, $1\le m,v_i,x_{i,j}\le n$, and $v_1,v_2,\dots,v_m$ are distinct, while $x_{i,1},x_{i,2},\dots,x_{i,a_i}$ are also distinct. **This problem has a large input, please use faster I/O methods.**