B. Последовательности И
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Последовательность $$$n$$$ ($$$n \ge 2$$$) неотрицательных целых чисел $$$a_1, a_2, \dots, a_n$$$ называется хорошей, если для всех $$$i$$$ от $$$1$$$ до $$$n-1$$$ выполняется следующее условие: $$$$$$a_1 \: \& \: a_2 \: \& \: \dots \: \& \: a_i = a_{i+1} \: \& \: a_{i+2} \: \& \: \dots \: \& \: a_n,$$$$$$ где $$$\&$$$ обозначает операцию побитового И.

Вам дан массив $$$a$$$ размера $$$n$$$ ($$$n \geq 2$$$). Найдите количество перестановок $$$p$$$ чисел от $$$1$$$ до $$$n$$$, для которых последовательность $$$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$$$.

Пример
Входные данные
4
3
1 1 1
5
1 2 3 4 5
5
0 2 0 3 0
4
1 3 5 1
Выходные данные
6
0
36
4
Примечание

В первом наборе входных данных все числа равны, поэтому все перестановки являются хорошими. Всего есть $$$6$$$ перестановок чисел от $$$1$$$ до $$$3$$$: $$$[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$$$.