Problem Description

Kame-kun has balls of $ N $ different colors.

The colors are numbered $1,\ 2,\ \ldots\ ,\ N$, and for each integer $i\ (1\ \le\ i\ \le\ N)$, there are $ A_i $ balls of color $ i $.

For each integer $k\ =\ 1,\ 2,\ \ldots\ ,\ M$, output the following value modulo $ 998244353 $.

• The total number of ways to put all the balls into $ k $ distinguishable boxes (here, it is allowed to have boxes with no balls in them)

Note that the way of putting balls is considered different if and only if there exists a box and a positive integer $ i $ such that the number of balls of color $ i $ in that box is different (in other words, balls of the same color are not distinguishable).

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ A_1 $ $ A_2 $ $\ldots$ $ A_N $

Output Format

Output $ M $ lines. The $ i $-th line should contain the answer for $k\ =\ i$.

Sample Input and Output

Sample Input #1

3 2
1 2 3

Sample Output #1

1
24

Sample Input #2

2 3
1 1

Sample Output #2

1
4
9

Sample Input #3

4 5
31415 92653 58979 32384

Sample Output #3

1
287242452
806145507
819893815
181831825

Notes/Hints

Constraints

• $1\ \le\ N\ \le\ 250000$
• $1\ \le\ M\ \le\ 100000$
• $1\ \le\ A_i\ <\ 998244353\ (1\ \le\ i\ \le\ N)$
• All inputs are integers

Sample Explanation 1

There is $ 1 $ ball of color $ 1 $, $ 2 $ balls of color $ 2 $, and $ 3 $ balls of color $ 3 $. For $ k=2 $, since the number of balls in one box determines the number in the other, the answer is $2\ \times\ 3\ \times\ 4\ =\ 24$.

Sample Explanation 3

Note that the output should be the remainder when divided by $ 998244353 $. Original idea: [MATH0]

见题面 Input 部分

见题面 Output 部分