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

在她最后一次出击之前，克洛伊向威尔姆提出了三个问题。

第三个问题是：当终结最终到来之时，谁将留下见证这一切？

威尔姆无法直接回答她。相反，他在黑板上画了一个圆，称之为“万物之环”，并在其上写下了 $n$ 个带标签的整数 $a_1,a_2,\ldots,a_n$。环上每一种可能的排列顺序，都对应着世界走向终结的一种不同方式。

考虑 $1$ 到 $n$ 的一个排列 $p_1,p_2,\ldots,p_n$。将对应的数字按此顺序放置在一个圆上。该环形排列的权重定义为：

$$\prod_{i=1}^{n}(a_{p_i}+a_{p_{i+1}}),$$

其中约定 $p_{n+1}=p_1$。

若一个排列可通过另一个排列进行循环移位得到，则这两个排列描述的是同一个环形排列。但将环形排列翻转（即取镜像）并不会使其与原排列相同；换言之，反射后的排列被视为不同的排列，除非它还能通过某个循环移位与原排列重合。

请计算所有互不相同的环形排列的权重之和。由于答案可能很大，请输出其对 $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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 2\cdot 10^5$）—— 表示带标签的整数个数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \le a_i \lt 998\,244\,353$）。

保证所有测试用例的 $n$ 之和不超过 $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$.

对于每个测试用例，输出一个整数——所有不同的环形排列的权重之和，对 $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$.

在第一个测试用例中，存在两种不同的环形排列。它们可分别由排列 $[1,2,3]$ 和 $[1,3,2]$ 表示。两者的权值均为

$$(1+2)(2+3)(3+1)=60,$$

因此答案为 $120$。

在第二个测试用例中，仅当 0 和 1 在圆周上交替出现时，排列才具有非零权值。满足该条件的环形排列共有

$$\frac{2\cdot3!\cdot3!}{6}=12$$

种：因子 $2$ 用于选择线性表示形式是以 0 还是以 1 开头，除以 $6$ 是为了将循环移位视为同一排列。每种排列的权值均为 $1$。其余所有排列的权值均为 $0$，因此答案为 $12$。