AT_arc223_b [ARC223B] Valid Arrays by K-Divisible Swaps

長さ $ N $ の整数列 $ A $ と正整数 $ K $ が与えられます。 $ A $ に対して、以下の操作を何回でも行うことができます。 - $ A_i+A_{i+1} $ が $ K $ で割り切れるような $ 1 $ 以上 $ N-1 $ 以下の整数 $ i $ を選び、 $ A_i $ と $ A_{i+1} $ を入れ替える。 操作を $ 0 $ 回以上行った後の $ A $ としてあり得る数列の総数を $ 998244353 $ で割った余りを求めてください。 $ 1 $ つの入力につき、 $ T $ 個のテストケースを解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケース $ \mathrm{case}_t $ は以下の形式で与えられる。 > $ N $ $ K $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

答えを合計 $ T $ 行で出力せよ。 $ t $ 行目には、 $ t $ 番目のテストケースの答えを出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースでは、操作を $ 0 $ 回以上行った後の $ A $ としてあり得る数列は $ (1,2,4,7),(1,4,2,7),(1,4,7,2),(2,1,4,7) $ の $ 4 $ つです。 ### 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 $ - すべてのテストケースにおける $ N $ の総和は $ 2 \times 10^5 $ 以下 - 入力される値はすべて整数