19026번 - Jump Jump Jump 다국어

The rabbit starts at point $(0, 0)$ on the plane. The are $k$ distinct vectors $(dx_1, dy_1)$, $(dx_2, dy_2)$, $\ldots$, $(dx_k, dy_k)$. On each step, the rabbit will choose one vector $(dx_c, dy_c)$ randomly with the same probability, and then jump from its current point $(x, y)$ to $(x + dx_c, y + dy_c)$. All choices are independent.

There are traps in all the lattice points $(x, x)$ for all $x \geq 1$. Once the rabbit jumps into a trap, it gets trapped and can not move anymore.

For each $x$ such that $1 \leq x \leq n$, output the probability that the rabbit gets trapped in the lattice point $(x, x)$.

The first line contains two integers $n$ and $k$ ($1 \leq n \leq 10^5$, $1 \leq k \leq 16$).

Each of the following $k$ lines contains two integers $dx_i$ and $dy_i$ ($0 \leq dx_i, dy_i \leq 3$) in each line. All the vectors are distinct.

Print $n$ lines. On line $x$, print the probability that the rabbit is trapped in the lattice point $(x, x)$. It is guaranteed that the probability can be represented as a fraction $A / B$ where $B$ is coprime to $998\,244\,353$, so output it as $A \cdot B^{-1} \bmod 998\,244\,353$.

The probabilities are $\frac{1}{2}, \frac{1}{8}, \frac{1}{16}, \frac{5}{128}, and \frac{7}{256}$.