题目描述

给定长度为 $n$ 的非负整数序列 $a_1, \ldots, a_n$，求：

$$\prod_{i=1}^n\prod_{j=i+1}^n(a_i\oplus a_j)$$

其中 $\oplus$ 表示按位异或运算。

答案对 $2^{64}$ 取模。

输入格式

本题输入包含多组数据。

第一行，一个整数 $T$，表示数据组数。对于每组数据：

• 第一行，一个整数 $n$。
• 第二行，$n$ 个整数 $a_1, \ldots, a_n$。

输出格式

对于每组数据，输出一行一个数，表示答案对 $2^{64}$ 取模后的结果。

4
2
1 1
3
1 2 3
5
1 4 5 2 6
13
1 2 3 4 5 6 7 8 9 10 11 12 13

0
6
423360
8286623314361712640

提示

【样例解释】

对于第一组数据，答案为 $a_1\oplus a_2=1\oplus 1=0$；

对于第二组数据，答案为 $(a_1\oplus a_2)\times (a_1\oplus a_3)\times (a_2\oplus a_3)=(1\oplus 2)\times(1\oplus 3)\times(2\oplus 3)=6$。

【数据范围】

本题采用捆绑测试。

对于所有数据，保证 $1\le T\le 10^5$，$2\le n,\sum n\le 10^6$，$0\le a_i<2^{64}$。

各子任务特殊限制如下：

子任务编号	$\sum n\le$	$a_i<$	分值
$1$	$5000$	$2^{64}$	$12$
$2$	$10^6$	$2^5$	$32$
$3$		$2^{64}$	$56$