Problem Description

Given a sequence of positive integers \( A_1, A_2, \cdots, A_N \), define \( S = N + \sum_{1 \leq i \leq N} A_i \).

Snuke the cat has \( S \) cards. Each card has an integer written on it, which are \( A_1, A_2, \cdots, A_N, -1, \cdots, -1 \). Specifically, there are \( \sum_{1 \leq i \leq N} A_i \) cards with \(-1\).

Snuke is currently standing at coordinate \( 0 \) on a number line. He will perform the following operation \( S \) times:

• Let \( x \) be the current coordinate. Choose one card from the remaining cards and discard it. Let \( v \) be the number written on the discarded card, then jump to coordinate \( x + v \). If the coordinate after the jump is \( 0 \), Snuke earns one coin.

For each \( k = 1, 2, \cdots, N \), find the number of distinct sequences of jumps such that Snuke earns exactly \( k \) coins, modulo \( 998244353 \).

Note that the sequences of jumps are counted. That is, if two cards have the same number, the operations of discarding them are considered identical.

Input Format

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

\( N \) \( A_1 \) \( A_2 \) \( \cdots \) \( A_N \)

Output Format

Output \( N \) lines. The \( i \)-th line should contain the answer for \( k = i \).

Sample Input and Output

Sample Input #1

2
1 1

Sample Output #1

2
4

Sample Input #2

3
1 2 3

Sample Output #2

140
220
144

Sample Input #3

20
16 6 15 19 1 9 6 1 11 7 6 12 3 11 11 18 10 9 15 5

Sample Output #3

507808441
401798892
110460932
680359166
737048635
442374434
737773176
980506765
473506608
693729211
532774651
621434128
4273369
839437048
585784927
590354055
969740008
825216624
442091194
660636013

Notes/Hints

Constraints

• \( 1 \leq N \leq 5000 \)
• \( 1 \leq A_i \leq 5000 \)
• All values in the input are integers.

Sample Explanation 1

For example, consider the sequence of jumps \( (-1, +1, +1, -1) \). In this case, Snuke's coordinates change as \( 0 \to -1 \to 0 \to 1 \to 0 \), earning 2 coins. Below are all possible sequences of jumps and the resulting number of coins earned:

• \( (-1, -1, +1, +1) \): 1 coin
• \( (-1, +1, -1, +1) \): 2 coins
• \( (-1, +1, +1, -1) \): 2 coins
• \( (+1, -1, -1, +1) \): 2 coins
• \( (+1, -1, +1, -1) \): 2 coins
• \( (+1, +1, -1, -1) \): 1 coin

见题面 Input 部分

见题面 Output 部分