CF2255F Who Will Witness the End?

Before her final sortie, Chtholly asks Willem three questions. The third is this: when the end finally comes, who will remain to witness it? Willem cannot answer her directly. Instead, he draws a circle on the board, calling it the ring of all things, and writes down $ n $ labeled integers $ a_1,a_2,\ldots,a_n $ . Every possible order around the ring describes a different way in which the world might reach its end. Consider a permutation $ p_1,p_2,\ldots,p_n $ of the integers from $ 1 $ to $ n $ . Place the corresponding numbers on a circle in this order. The weight of the resulting circular arrangement is $$$ \prod_{i=1}^{n}(a_{p_i}+a_{p_{i+1}}), $$$ where $ p_{n+1}=p_1 $ . Two permutations describe the same circular arrangement if one can be obtained from the other by a cyclic shift. Reversing an arrangement does not make it the same arrangement; in other words, reflected arrangements are considered different unless they also coincide after a cyclic shift. Find the sum of the weights of all distinct circular arrangements. Since the answer may be large, output it modulo $ 998\,244\,353 $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains one integer $ n $ ( $ 3 \le n \le 2\cdot 10^5 $ ) — the number of labeled integers. The second line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 0 \le a_i \lt 998\,244\,353 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

For each test case, output one integer — the sum of the weights of all distinct circular arrangements, modulo $ 998\,244\,353 $ .

In the first test case, there are two distinct circular arrangements. They can be represented by the permutations $ [1,2,3] $ and $ [1,3,2] $ . Both have weight $$$ (1+2)(2+3)(3+1)=60, $$$ so the answer is $ 120 $ . In the second test case, an arrangement has nonzero weight only if zeros and ones alternate around the circle. There are $$$ \frac{2\cdot3!\cdot3!}{6}=12 $$$ such circular arrangements: the factor $ 2 $ chooses whether a linear representative starts with a zero or a one, and division by $ 6 $ identifies cyclic shifts. Each arrangement has weight $ 1 $ . All other arrangements have weight $ 0 $ , so the answer is $ 12 $ .