Последовательность \(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\) строк, где \(i\)-я строка содержит количество хороших перестановок в \(i\)-м наборе входных данных по модулю \(10^9 + 7\).
Примечание
В первом наборе входных данных все числа равны, поэтому все перестановки являются хорошими. Всего есть \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|