AT_arc223_b.Valid Arrays by K-Divisible Swaps

You are given an integer sequence $A$ of length $N$ and a positive integer $K$.
You can perform the following operation on $A$ any number of times:

• Choose an integer $i$ with $1 \leq i \leq N-1$ such that $A_i + A_{i+1}$ is divisible by $K$, and swap $A_i$ and $A_{i+1}$.

Find the total number, modulo $998244353$, of distinct sequences that $A$ can become after performing the operation zero or more times.

Solve $T$ test cases per input.

给你一个长度为 $N$ 的整数序列 $A$ 和一个正整数 $K$。
你可以对 $A$ 执行以下操作任意多次：

• 选择一个满足 $1 \leq i \leq N-1$ 的整数 $i$，使得 $A_i + A_{i+1}$ 能被 $K$ 整除，然后交换 $A_i$ 和 $A_{i+1}$。

求在执行零次或多次上述操作后，$A$ 可能变成的不同序列的总数（对 $998244353$ 取模）。

每组输入包含 $T$ 个测试用例。

The input is given from Standard Input in the following format:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case $\mathrm{case}_t$ is given in the following format:

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

输入从标准输入中按以下格式给出：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例 $\mathrm{case}_t$ 的格式如下：

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

Output the answers over a total of $T$ lines. The $t$-th line should contain the answer for the $t$-th test case.

在总共 $T$ 行中输出答案。第 $t$ 行应包含第 $t$ 个测试用例的答案。

Sample 1 Explanation:
For the first test case, the sequences that $A$ can become after performing the operation zero or more times are these four: $(1,2,4,7),(1,4,2,7),(1,4,7,2),(2,1,4,7)$.

Constraints

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 10^9$
• $1 \leq A_i \leq 10^9$
• The sum of $N$ over all test cases is at most $2 \times 10^5$.
• All input values are integers.

样例 1 解释：
对于第一个测试用例，序列 $A$ 在执行零次或多次操作后可能变成以下四种序列：$(1,2,4,7)$、$(1,4,2,7)$、$(1,4,7,2)$、$(2,1,4,7)$。

约束条件

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 10^9$
• $1 \leq A_i \leq 10^9$
• 所有测试用例的 $N$ 之和不超过 $2 \times 10^5$。
• 所有输入值均为整数。