P1054遗失的赋值（assign）

【题目描述】

小 X 在整理旧档案时找到了一份赋值记录。记录原本写有一个长度为 $n$ 的 $01$ 序列 $x_1,x_2,\ldots,x_n$，但每个位置的具体赋值已经遗失，只留下了若干核对结果。

对于每个 $1\leq i\leq n-k+1$，记录中保存了一个整数 $s_i$。它表示从位置 $i$ 开始的连续 $k$ 个位置之和，即 $s_i=\sum_{j=i}^{i+k-1}x_j$。

记录中还写明，整个序列恰好有 $m$ 个位置的值为 $1$。

小 X 希望补全这些遗失的赋值。两个 $01$ 序列不同，当且仅当存在至少一个位置在两个序列中的取值不同。

请你求出同时符合全部记录的不同 $01$ 序列数量。答案可能很大，请对 $998{,}244{,}353$ 取模。

【输入格式】

从文件 $\textbf{\textit{assign.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含三个整数 $n,k,m$，分别表示序列长度、连续区间长度与序列中 $1$ 的数量。

第二行包含 $n-k+1$ 个整数 $s_1,s_2,\ldots,s_{n-k+1}$，表示每个长度为 $k$ 的连续区间的元素之和。

【输出格式】

输出到文件 $\textbf{\textit{assign.out}}$ 中。

对于每组测试数据，输出一行一个非负整数，表示符合记录的不同 $01$ 序列数量对 $998{,}244{,}353$ 取模后的结果。

【样例 1 输入】

10 224 2 231 1 145 2 352 1 1 1

【样例 1 输出】

1221

【说明/提示】

【样例 1 解释】

对于第一组测试数据，符合记录的序列为 $(0,1,0,1)$ 与 $(1,0,1,0)$。

对于第二组测试数据，只有序列 $(1,1,0,1,0)$ 符合记录。

【样例 2】

见选手目录下的 $\textbf{\textit{assign/assign2.in}}$ 和 $\textbf{\textit{assign/assign2.ans}}$。

该组样例符合测试点 $1\sim2$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{assign/assign3.in}}$ 和 $\textbf{\textit{assign/assign3.ans}}$。

该组样例符合测试点 $3\sim5$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{assign/assign4.in}}$ 和 $\textbf{\textit{assign/assign4.ans}}$。

该组样例符合测试点 $6\sim9$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{assign/assign5.in}}$ 和 $\textbf{\textit{assign/assign5.ans}}$。

该组样例符合测试点 $10\sim15$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{assign/assign6.in}}$ 和 $\textbf{\textit{assign/assign6.ans}}$。

该组样例符合测试点 $16\sim20$ 的数据范围。

\newpage

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq k\leq n\leq10^6$，单个测试点内所有测试数据满足 $\sum n\leq10^6$。

特殊性质 A：保证 $k\leq20$。

特殊性质 B：保证 $n$ 是 $k$ 的倍数。

对于所有测试数据，保证：

• $0\leq c\leq20$，$1\leq T\leq10$。
• $0\leq m\leq n$。
• 对于所有 $1\leq i\leq n-k+1$，均有 $0\leq s_i\leq k$。