Вам дан массив \(a\), состоящий из \(n\) различных целых положительных чисел.
Рассмотрим бесконечное множество целых чисел \(S\), содержащее все целые числа \(x\), удовлетворяющие хотя бы одному из следующих условий:
- \(x = a_i\) для некоторого \(1 \leq i \leq n\).
- \(x = 2y + 1\) и \(y\) находится в \(S\).
- \(x = 4y\) и \(y\) находится в \(S\).
Например, если \(a = [1,2]\), то \(10\) наименьших элементов в \(S\) будут равны \(\{1,2,3,4,5,7,8,9,11,12\}\) .
Найдите количество элементов в \(S\), строго меньших, чем \(2^p\). Так как это число может быть слишком большим, выведите его по модулю \(10^9 + 7\).
Выходные данные
Выведите единственное целое число — количество элементов в \(S\), строго меньших \(2^p\). Не забудьте вывести его по модулю \(10^9 + 7\).
Примечание
В первом примере элементы меньше \(2^4\) равны \(\{1, 3, 4, 6, 7, 9, 12, 13, 15\}\).
Во втором примере элементы меньше \(2^7\) равны \(\{5,11,20,23,39,41,44,47,79,80,83,89,92,95\}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 4
6 1
|
9
|
|
2
|
4 7
20 39 5 200
|
14
|
|
3
|
2 200000
48763 1000000000
|
448201910
|