Background

Unknown, the terrifying Cat-demon, is the archenemy of “Furrmes”.

One day, she saw an elementary-school math olympiad problem online: the Josephus problem.

Problem Description

Unknown is going to commit another crime. She makes $n$ cats stand in a line. From left to right, their initial labels are $1,2,\dots,n$. At the same time, each cat initially stands on the cell with the same number as its label.

Unknown has $k+1$ favorite numbers $t_0,t_1,\dots,t_k$. They satisfy:

• $t_0=1$.
• For $1\le i\le k$, $t_{i-1}<t_i$.
• $t_k\le n$.

Unknown will pet cats for $n-1$ rounds. In each round, she will pet exactly one cat. One “petting” follows these rules:

1. Randomly choose a number $i$ from $0$ to $k$.
2. If there is currently a cat standing on cell $t_i$, Unknown will pet that cat. Then the cat will run away from the cells and will no longer participate in any later process, and proceed to Step 3. Otherwise, go back to Step 1.
3. Let all remaining cats run to new cells. If there are $p$ cats at this moment, they will line up onto cells $[1,p]$ while keeping their relative order unchanged.

However, although cats are cute, both the cats and Unknown can get tired of this. So when only one cat is left, Unknown will stop petting. Please compute, for each cat, the probability that it is not petted in the end.

Output the final answers modulo $998244353$.

Input Format

The first line contains two integers $n$ and $k$, meaning there are $n$ cats in total, and Unknown has $k+1$ favorite numbers.

The second line contains $k$ integers, representing $t_1$ through $t_k$, separated by spaces.

Output Format

Output one line with $n$ integers. The $i$-th integer is the probability that the cat with initial label $i$ is not petted, separated by spaces, taken modulo $998244353$.

2 0

0 1 

4 1 
3 

0 748683265 748683265 499122177 

8 3 
3 6 8 

0 291154603 291154603 582309206 166374059 166374059 748683265 748683265 

Hint

Sample Explanation:

In the first sample, Unknown only likes the number $1$, so each time she will definitely pet the current first cat. Therefore, the first cat will surely be petted, and the second cat will surely not be petted.

In the second sample, from left to right, the probabilities that the four cats are not petted are $0,\frac{1}{4},\frac{1}{4},\frac{1}{2}$.

Constraints:

This problem uses bundled testdata.

For all testdata, it is guaranteed that $1\le n,k\le10^6$, and the range of $t_i$ is as described above.

Postscript:
Peanut: So what is Unknown’s real name?
Furrmes: I don’t know, so she is called Unknown.
Peanut: ?

Translated by ChatGPT 5