Statement : G. Stop Spot

G. Stop Spot

You are given an array $a$ of size $n$ ($1 \leq a_i \leq m$).

Consider all $m!$ permutations of the array $[1, 2, \ldots, m]$. For any permutation $p$, define the array $b_p$ as the array formed by concatenating the array $a$ and the permutation $p$. More formally, $b_p = [a_1, a_2, \ldots, a_n, p_1, p_2, \ldots, p_m]$.

Let $f(i)$ denote the number of permutations $p$ such that the array $b_p$ contains exactly $i$ palindromic$^{\text{∗}}$ subarrays of even length.

Your task is to compute $$$ \sum_{i=0}^{10^{100}} f(i)^{i+1}.$

Since the answer may be large, it should be computed modulo $998\,244\,353$.

$^{\text{∗}}$An array $[c_1, c_2, \ldots, c_k]$ is said to be palindromic if $c_i = c_{k+1-i}$ for all $1 \le i \le k$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each testcase contains two integers $n$ and $m$ ($1 \le m \le n \le 10^6$).

The second line of each testcase contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le m$) — the elements of the array.

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

Output

For each testcase, print a single integer on a new line — $ \sum_{i=0}^{10^{100}} f(i)^{i+1}$ modulo $998\,244\,353$.

Example

Input

5
4 3
3 1 2 1
1 1
1
9 4
4 1 2 1 3 3 1 2 1
6 3
1 1 3 1 1 1
10 6
4 4 1 2 1 3 3 1 2 1

Output

Note

Note

In the first test case, $n=4$, $m=3$, and $a=[3,1,2,1]$.

Let’s list all permutations and calculate the number of palindromic subarrays of even length:

$p_1 = [1, 2, 3]$, $b_{p_1} = [3, 1, 2, 1, 1, 2, 3]$, and the number of palindromic subarrays of even length is $2$.
$p_2 = [1, 3, 2]$, $b_{p_2} = [3, 1, 2, 1, 1, 3, 2]$, and the number of palindromic subarrays of even length is $1$.
$p_3 = [2, 1, 3]$, $b_{p_3} = [3, 1, 2, 1, 2, 1, 3]$, and the number of palindromic subarrays of even length is $0$.
$p_4 = [2, 3, 1]$, $b_{p_4} = [3, 1, 2, 1, 2, 3, 1]$, and the number of palindromic subarrays of even length is $0$.
$p_5 = [3, 1, 2]$, $b_{p_5} = [3, 1, 2, 1, 3, 1, 2]$, and the number of palindromic subarrays of even length is $0$.
$p_6 = [3, 2, 1]$, $b_{p_6} = [3, 1, 2, 1, 3, 2, 1]$, and the number of palindromic subarrays of even length is $0$.

Thus, we have $f(0) = 4$, $f(1) = 1$, $f(2) = 1$, and $f(i) = 0$ for all $i \gt 2$. Hence, the answer is $4^1 + 1^2 + 1^3 = 6$.