P14890 Yummy

给定一个长度为 $n$ 的序列 $s$ 和一个正整数 $k$，其中 $s_i \in \{-1,1\}$，即 $s_i$ 为 $-1$ 或 $1$。 我们称一个长度为 $n$ 的序列 $v$ 是 Yummy 的，当且仅当序列 $v$ 中的每个元素**均为不大于 $\boldsymbol{k}$ 的非负整数**，且满足： $$ \sum_{i=1}^n s_i\cdot v_i\cdot k^i=0 $$ 即对于所有不大于 $n$ 的正整数 $i$，$s_i \cdot v_i \cdot k^i$ 之和为 $0$。 你需要求出不同的长度为 $n$ 的 Yummy 的序列 $v$ 的数量。其中，我们称两个长度均为 $m$ 的序列 $a,b$ 是不同的，当且仅当存在至少一个不大于 $m$ 的正整数 $i$ 满足 $a_i\ne b_i$。 由于答案可能很大，所以你只需要求出答案对 $998244353$ 取模的结果。

**本题有多组测试数据**。 输入文件的第一行输入一个正整数 $T$（$1 \leq T \leq 10^4$） 表示测试数据组数。 接下来，对于每一组测试数据： 第一行输入两个正整数 $n$（$2 \leq n \leq 5 \times 10^5$）和 $k$（$2 \leq k \leq 10^9$）。 第二行输入 $n$ 个整数 $s_i$（$s_i \in \{-1,1\}$）。 保证对于单个测试点，所有 $n$ 的和不超过 $5\times 10^5$。

对于每组测试数据，输出一行一个正整数表示答案对 $998244353$ 取模的结果。