Given a sequence $s$ of length $n$ and a positive integer $k$, where $s_i \in \{-1, 1\}$, i.e., $s_i$ is either $-1$ or $1$.

A sequence $v$ of length $n$ is called Yummy if and only if every element in $v$ is a non-negative integer no greater than $k$, and it satisfies:

$$ \sum_{i=1}^n s_i\cdot v_i\cdot k^i=0 $$

That is, the sum of $s_i \cdot v_i \cdot k^i$ for all positive integers $i$ no greater than $n$ is $0$.

You need to find the number of distinct Yummy sequences $v$ of length $n$. Two sequences $a$ and $b$ of length $m$ are considered distinct if and only if there exists at least one positive integer $i$ no greater than $m$ such that $a_i \neq b_i$.

Since the answer may be very large, you only need to output the answer modulo $998244353$.

Input

This problem contains multiple test cases.

The first line of the input contains a positive integer $T$ ($1 \leq T \leq 10^4$), representing the number of test cases.

For each test case:

The first line contains two positive integers $n$ ($2 \leq n \leq 5 \times 10^5$) and $k$ ($2 \leq k \leq 10^9$).

The second line contains $n$ integers $s_i$ ($s_i \in \{-1, 1\}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \times 10^5$.

Output

For each test case, output a single line containing a positive integer representing the answer modulo $998244353$.

Examples

Input 1

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

Output 1

5
16

Note

For the first test case, the sequences $v$ that satisfy the condition are:

• $\{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\}$.