C - Whole Product of Pairwise Distances 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

N 個の正整数からなる数列 A が与えられます。
\prod_{1 \leq i < j \leq N}|A_i-A_j| を N で割った余りを求めてください。

1 つの入力につき、T 個のテストケースを解いてください。

制約

  • 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 以下
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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

各テストケース \mathrm{case}_t は以下の形式で与えられる。

N  
A_1 A_2 \ldots A_N

出力

答えを合計 T 行で出力せよ。 t 行目には、t 番目のテストケースの答えを出力せよ。

入力例 1

3
3
1 9 5
3
2 2 3
5
11 33 22 55 44

出力例 1

2
0
3

1 つ目のテストケースについて、|A_1-A_2| \times |A_1-A_3| \times |A_2-A_3|=8 \times 4 \times 4=128 であり、これを 3 で割った余りは 2 です。

Score : 500 points

Problem Statement

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.

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.

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

Output

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

Sample Input 1

3
3
1 9 5
3
2 2 3
5
11 33 22 55 44

Sample Output 1

2
0
3

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.