CF2226G Stop Spot

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

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

For each testcase, print a single integer on a new line — $ \sum_{i=0}^{10^{100}} f(i)^{i+1} $ modulo $ 998\,244\,353 $ .

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