Областная олимпиада по информатике 2020 года за 10 класс | Казахстанские олимпиады

Задача D. From And with love

Ограничение по времени Ограничение по памяти
1 секунда 256 мегабайт

Абай очень любит массивы. Еще больше он любит играть с подпоследовательностями массива. Подпоследовательность — это такая последовательность массива, которая может быть получена удалением нескольких (возможно ноль) элементов из этого массива. Вам дан массив AA из NN целых чисел. Рассмотрим какую--нибудь подпоследовательность массива. Пусть битовый AND этой подпоследовательности равен XX. Тогда подпоследовательность называется хорошей, если в ней нет элемента со значением XX. Посчитайте количество хороших подпоследовательностей.

Формат входного файла

В первой строке дается натуральное число NN — размер массива AA. В следующей строке заданы NN целых неотрицательных чисел — элементы массива AA.

Формат выходного файла

Выведите одно число — количество хороших подпоследовательностей. Так как ответ может быть достаточно большим, выведите его остаток от деления на 109+710^9 + 7.

Примеры

Вход

5
0 2 5 3 7

Выход

6