题目描述

给定一个长度为 $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$ 取模的结果。

样例

样例输入 1

2
5 2
-1 1 1 -1 -1
8 100
1 1 -1 -1 -1 -1 1 -1

样例输出 1

5
16

样例解释

对于第一组测试数据，满足条件的序列 $v$ 有：

• $\{0,0,0,0,0\}$；
• $\{0,0,2,1,0\}$；
• $\{0,2,1,1,0\}$；
• $\{2,1,0,0,0\}$；
• $\{2,1,2,1,0\}$。