AT_arc223_c.Whole Product of Pairwise Distances

You are given a sequence $A$ of $N$ positive integers.
Find the remainder when $\prod_{1 \leq i < j \leq N}|A_i-A_j|$ is divided by $N$.

Solve $T$ test cases per input.

给你一个长度为 $N$ 的正整数序列 $A$。
求 $\prod_{1 \leq i < j \leq N}|A_i-A_j|$ 除以 $N$ 的余数。

每组输入包含 $T$ 个测试用例。

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$
$A_1$ $A_2$ $\ldots$ $A_N$

输入从标准输入中按以下格式给出：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例 $\mathrm{case}_t$ 按以下格式给出：

$N$
$A_1$ $A_2$ $\ldots$ $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.

在总共 $T$ 行中输出答案。第 $t$ 行应包含第 $t$ 个测试用例的答案。

Sample 1 Explanation:
For the first test case, $|A_1-A_2| \times |A_1-A_3| \times |A_2-A_3|=8 \times 4 \times 4=128$, and the remainder when this is divided by $3$ is $2$.

Constraints

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 2 \times 10^5$
• $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.

样例 1 解释：
对于第一个测试用例，$|A_1-A_2| \times |A_1-A_3| \times |A_2-A_3|=8 \times 4 \times 4=128$，该值除以 $3$ 的余数为 $2$。

约束条件

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• 所有测试用例的 $N$ 之和不超过 $2 \times 10^5$。
• 所有输入值均为整数。