AT_arc223_b [ARC223B] 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.

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 $

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

### Sample Explanation 1 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.