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}$.