Однажды Divan проанализировал последовательность \(a_1, a_2, \ldots, a_n\), состоящую из \(n\) целых неотрицательных чисел, следующим образом. Он рассмотрел все непустые подпоследовательности последовательности \(a\), вычислил побитовое исключающее ИЛИ её элементов, после чего просуммировал все полученные результаты, получив удобство последовательности \(a\).
Напомним, что последовательность \(c\) является подпоследовательностью последовательности \(d\), если \(c\) может быть получена из \(d\) путем удаления нескольких элементов (возможно, ни одного). Например, \([1, \, 2, \, 3, \, 4]\), \([2, \, 4]\) и \([2]\) являются подпоследовательностями \([1, \, 2, \, 3, \, 4]\), а \([4, \, 3]\) и \([0]\) не являются.
Divan очень гордился проведенным анализом, но теперь потерял и последовательность \(a\), и значение ее удобства! Однако Divan помнит значение побитового ИЛИ на \(m\) непрерывных подотрезках последовательности \(a\). Оказалось, что каждый элемент последовательности входит хотя бы в один из этих \(m\) отрезков.
Divan просит вас найти удобство последовательности \(a\), используя информацию, которую он помнит. Если возможны несколько значений удобства, выведите любое.
Так как ответ может быть большим, выведите его по модулю \(10^9 + 7\).
Выходные данные
Для каждого набора входных данных выведите любое возможное удобство последовательности \(a\) по модулю \(10^9 + 7\).
Примечание
В первом примере одной из последовательностей, которая подходит под ограничения, является \([0, 2]\). Рассмотрим все её непустые подпоследовательности:
- \([0]\): побитовое исключающее ИЛИ равно \(0\);
- \([2]\): побитовое исключающее ИЛИ равно \(2\);
- \([0, 2]\): побитовое исключающее ИЛИ равно \(2\).
Суммируя полученные числа, получаем \(4\), что является ответом.
Во втором примере одной из последовательностей, которая подходит под ограничения, является \([0, \, 5, \, 5]\).
В третьем примере одной из последовательностей, которая подходит под ограничения, является \([5, \, 6, \, 7, \, 0, \, 2]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 1
1 2 2
3 2
1 3 5
2 3 5
5 4
1 2 7
3 3 7
4 4 0
4 5 2
|
4
20
112
|