Cat's Lucky Touch

In this problem, there are n cats standing in a line. Initially, they are labeled from 1 to n and the cat with label i stands in cell i. You are also given k+1 favorite numbers \(t_0, t_1, \dots, t_k\) satisfying:

• \(t_0 = 1\)
• \(t_{i-1} < t_i\) for \(1 \le i \le k\)
• \(t_k \le n\)

Then, the following process takes place for exactly \(n-1\) rounds (i.e. until only one cat remains):

1. A number \(i\) is chosen uniformly at random from \(\{0,1,\dots,k\}\). (In other words, one of the favorite positions is chosen at random.)
2. If there is a cat standing in cell \(t_i\) (recall that the current line-up has cells numbered from \(1\) to the current number of cats), then that cat is touched and removes itself from the line. Otherwise, step 1 is repeated.
3. After a cat is removed, the remaining cats run and reoccupy cells \(1,2,\dots,p\) (where \(p\) is the new total) while keeping their relative order.

The process stops immediately when only one cat remains. For each cat, compute the probability that it is never touched (i.e. it is the final surviving cat). Output the answer modulo \(998244353\).

Note: In every round, the valid removal positions are determined by the set \(S(p)=\{t_j: t_j\le p\}\). In a round when there are p cats, let \(m = |S(p)|\). Then, among these \(m\) positions, if a cat is at position \(j\), it will be removed if and only if \(j\) equals one of the chosen \(t_i\). If \(j\) is greater than the chosen index, its position remains the same; if it is less, its index decreases by 1. Thus, if we let \(dp(p, j)\) be the probability that a cat which is at position \(j\) when there are p cats eventually survives, the recurrence is:

[ dp(p, j) = \frac{1}{m} \Bigl(\Bigl(m - #{x \in S(p) : x \le j}\Bigr) \cdot dp(p-1, j) + \Bigl(#{x \in S(p) : x < j}\Bigr) \cdot dp(p-1, j-1)\Bigr) ]

with the base case \(dp(1,1)=1\). Initially, since the cats are in order, the i-th cat is at position \(i\). Thus, the answer for the i-th cat is \(dp(n, i)\).

inputFormat

The first line contains two integers \(n\) and \(k\).

The second line contains \(k+1\) integers: \(t_0, t_1, \dots, t_k\), where \(t_0=1\), \(t_{i-1} < t_i\) for \(1\le i\le k\) and \(t_k\le n\).

Initially, the n cats are arranged from left to right at cells \(1,2,\dots,n\) (the i-th cat is in cell \(i\)).

outputFormat

Output n integers separated by spaces, where the i-th integer is the probability (modulo \(998244353\)) that the i-th cat is the final surviving cat.

sample

2 0
1

0 1