$$$n$$$ 非负整数序列 ($$$n \ge 2$$$) $$$a_1, a_2, \dots, a_n$$$ 被称为良好,如果对于从 $$$1$$$ 到 $$$n-1$$$ 的所有 $$$i$$$ 满足以下条件: $$$$$$a_1 \: \& \: a_2 \: \& \: \dots \: \& \: a_i = a_{i+1} \: \& \: a_{i+2} \: \& \: \dots \: \& \: a_n,$$$$$$ 其中 $$$\&$$$ 表示按位 AND 运算。
给定一个数组 $$$a$$$,大小为 $$$n$$$ ($$$n \geq 2$$$)。求从 $$$1$$$ 到 $$$n$$$ 的数字的排列 $$$p$$$ 的数量,其中序列 $$$a_{p_1}$$$, $$$a_{p_2}$$$, ... ,$$$a_{p_n}$$$ 是好的。由于这个数字可能很大,因此输出它对 $$$10^9+7$$$ 取模。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$),表示测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 数组的大小。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — 数组的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
输出 $$$t$$$ 行,其中第 $$$i$$$ 行包含第 $$$i$$$ 测试用例中良好排列的数量,以 $$$10^9 + 7$$$ 为模。
示例
输入 #1
4 3 1 1 1 5 1 2 3 4 5 5 0 2 0 3 0 4 1 3 5 1
输出 #1
6 0 36 4
注意
在第一个测试用例中,由于所有数字都相等,因此无论我们采用何种排列,序列都是好的。从 $$$1$$$ 到 $$$3$$$ 的数字总共有 $$$6$$$ 可能的排列: $$$[1,2,3]$$$, $$$[1,3,2]$$$, $$$[2,1,3]$$$, $$$[2,3,1]$$$, $$$[3,1,2]$$$, $$$[3,2,1]$$$。
在第二个测试用例中,可以证明不存在序列良好的排列。
在第三个测试用例中,总共有 $$$36$$$ 排列是良好的序列。其中之一是排列 $$$[1,5,4,2,3]$$$,它产生序列 $$$s=[0,0,3,2,0]$$$。这是一个很好的序列,因为
- $$$ s_1 = s_2 \: \& \: s_3 \: \& \: s_4 \: \& \: s_5 = 0$$$,
- $$$ s_1 \: \& \: s_2 = s_3 \: \& \: s_4 \: \& \: s_5 = 0$$$,
- $$$ s_1 \: \& \: s_2 \: \& \: s_3 = s_4 \: \& \: s_5 = 0$$$,
- $$$ s_1 \: \& \: s_2 \: \& \: s_3 \: \& \: s_4 = s_5 = 0$$$。