AT_arc232_e.Doubling

You are given a sequence of non-negative integers of length $N+1$, $X=(X_1,X_2,\ldots,X_{N+1})$, where $X_{N+1}=0$.

You can perform the following operation.

• Choose an integer $i$ satisfying $1 \leq i \leq N$ and $X_i \geq 1$, subtract $1$ from $X_i$, and add $2$ to $X_{i+1}$.

You are given an integer $K$. For each $k=1,2,\ldots,K$, find the number, modulo $998244353$, of sequences that can result from performing the operation exactly $k$ times on the given sequence.

给你一个长度为 $N+1$ 的非负整数序列 $X=(X_1,X_2,\ldots,X_{N+1})$，其中 $X_{N+1}=0$。

你可以执行以下操作：

• 选择一个满足 $1 \leq i \leq N$ 且 $X_i \geq 1$ 的整数 $i$，将 $X_i$ 减 $1$，并将 $X_{i+1}$ 加 $2$。

给定一个整数 $K$。对每个 $k=1,2,\ldots,K$，求在给定序列上恰好执行 $k$ 次该操作后所能得到的不同序列的个数（对 $998244353$ 取模）。

The input is given from Standard Input in the following format. $X_{N+1}$ is not included in the input.

$N$ $K$
$X_1$ $X_2$ $\ldots$ $X_N$

输入从标准输入给出，格式如下。$X_{N+1}$ 不包含在输入中。

$N$ $K$
$X_1$ $X_2$ $\ldots$ $X_N$

Output the answers for $k=1,2,\cdots,K$ in this order, separated by spaces, on a single line.

按顺序输出 $k=1,2,\cdots,K$ 对应的答案，答案之间用空格分隔，放在一行中。

Sample 1 Explanation:
The sequences that can result from performing the operation once are $(0,3,0)$ and $(1,0,2)$, so there are two of them. The only sequence that can result from performing the operation twice is $(0,2,2)$, so there is one. Multiple orders of operations yield this sequence, but it is counted as one sequence.

Sample 2 Explanation:
The initial sequence is $(1,0,0)$. With each operation, the sequence changes to $(0,2,0)$, $(0,1,2)$, $(0,0,4)$. The operation cannot be performed four times.

Constraints

• $1 \leq N \leq 20$
• $1 \leq K \leq 250000$
• $0 \leq X_i \leq 250000$ $(1 \leq i \leq N)$
• $X_{N+1}=0$
• All input values are integers.

样例 1 解释：
执行一次操作后可能得到的序列为 $(0,3,0)$ 和 $(1,0,2)$，共两个。执行两次操作后唯一可能得到的序列为 $(0,2,2)$，仅一个。尽管存在多种操作顺序可得到该序列，但它仅被计为一个序列。

样例 2 解释：
初始序列为 $(1,0,0)$。每次执行操作后，序列依次变为 $(0,2,0)$、$(0,1,2)$、$(0,0,4)$。无法执行四次操作。

约束条件

• $1 \leq N \leq 20$
• $1 \leq K \leq 250000$
• $0 \leq X_i \leq 250000$ $(1 \leq i \leq N)$
• $X_{N+1}=0$
• 所有输入值均为整数。