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$$$.

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$$$.

Stop Spot

Examples