← 返回题目列表

Codeforces · 1513/B

B. AND 序列

中文机器翻译题面 查看原题

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