D. RestORe
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим последовательность целых неотрицательных чисел от $$$L$$$ до $$$R$$$ включительно. Разобьем такую последовательность на $$$n$$$ непустых отрезков и посчитаем побитовое «или» чисел в каждом отрезке. Результат для $$$i$$$-го отрезка назовем $$$f_i$$$.

Решите обратную задачу: по числам $$$f_1, f_2, \ldots, f_n$$$ найдите количество способов выбрать $$$L$$$ и $$$R$$$, а затем разбить все числа от $$$L$$$ до $$$R$$$ на $$$n$$$ непустых отрезков так, чтобы результаты вычисления побитового «или» в каждом отрезке были равны $$$f_1, f_2, \ldots, f_n$$$ соответственно.

Побитовое «или» (or) двух целых неотрицательных чисел вычисляется следующим образом: запишем оба числа в двоичной системе счисления, $$$i$$$-й двоичный разряд результата равен $$$1$$$, если у хотя бы одного из аргументов он равен $$$1$$$. Например, $$$(17 \mathbin{|} 13) = (10001_2 \mathbin{|} 01101_2) = 11101_2 = 29$$$.

Входные данные

В первой строке содержится число $$$n$$$ ($$$1 \le n \le 200\,000$$$). В следующей строке содержатся $$$n$$$ чисел $$$f_i$$$ ($$$0 \le f_i \lt 2^{60}$$$).

Выходные данные

Выведите одно число — количество способов выбрать последовательность из подряд идущих чисел и разбить ее на $$$n$$$ отрезков. Поскольку ответ может быть большим, выведите его по модулю $$$1\,000\,000\,007$$$.

Система оценки
ПодзадачаБаллыОграничения
116$$$n = 1$$$
212$$$n \le 16$$$, $$$0 \le f_ilt; 16$$$
313$$$n \le 256$$$, $$$0 \le f_ilt; 256$$$
418$$$n \le 1024$$$, $$$0 \le f_ilt; 1024$$$
524$$$n \le 30\,000$$$, $$$0 \le f_ilt; 2^{30}$$$
617Без дополнительных ограничений
Примеры
Входные данные
3
0 7 7
Выходные данные
4
Входные данные
1
11
Выходные данные
6
Входные данные
2
4 6
Выходные данные
0
Примечание

В первом примере существует четыре способа разбить массив подряд идущих чисел на три части, так, чтобы побитовые «или» в них были равны $$$0$$$, $$$7$$$ и $$$7$$$ соответственно:

  • $$$[0], [1, 2, 3, 4, 5, 6], [7]$$$: $$$0 = 0$$$; $$$1 \mathbin{|} 2 \mathbin{|} 3 \mathbin{|} 4 \mathbin{|} 5 \mathbin{|} 6 = 7$$$; $$$7 = 7$$$
  • $$$[0], [1, 2, 3, 4, 5], [6, 7]$$$: $$$0 = 0$$$; $$$1 \mathbin{|} 2 \mathbin{|} 3 \mathbin{|} 4 \mathbin{|} 5 = 7$$$; $$$6 \mathbin{|} 7 = 7$$$
  • $$$[0], [1, 2, 3, 4], [5, 6, 7]$$$: $$$0 = 0$$$; $$$1 \mathbin{|} 2 \mathbin{|} 3 \mathbin{|} 4 = 7$$$; $$$5 \mathbin{|} 6 \mathbin{|} 7 = 7$$$
  • $$$[0], [1, 2, 3, 4], [5, 6]$$$: $$$0 = 0$$$; $$$1 \mathbin{|} 2 \mathbin{|} 3 \mathbin{|} 4 = 7$$$; $$$5 \mathbin{|} 6 = 7$$$