AT_arc223_b [ARC223B] Valid Arrays by K-Divisible Swaps

给定一个长度为 $N$ 的整数序列 $A$，以及一个正整数 $K$。 你可以对 $A$ 执行如下操作任意次： - 选择一个整数 $i$，满足 $1 \leq i \leq N-1$，且 $A_i + A_{i+1}$ 能被 $K$ 整除，然后交换 $A_i$ 和 $A_{i+1}$ 的位置。 请你求出，经过若干次操作（可以为零）后，序列 $A$ 可能变成的本质不同序列的总数。由于答案可能很大，请对 $998244353$ 取模。 对于每组输入，请解决 $T$ 组测试用例。

输入从标准输入读入，格式如下： > $T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$ 每组测试用例 $\mathrm{case}_t$ 的格式如下： > $N$ $K$ $A_1$ $A_2$ $…$ $A_N$

共输出 $T$ 行，第 $t$ 行输出第 $t$ 组测试用例的答案。

### 样例解释 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$。 - 所有输入值均为整数。 由 ChatGPT 5 翻译