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

Вам дан массив $$$a$$$, состоящий из $$$n$$$ различных целых положительных чисел.

Рассмотрим бесконечное множество целых чисел $$$S$$$, содержащее все целые числа $$$x$$$, удовлетворяющие хотя бы одному из следующих условий:

  1. $$$x = a_i$$$ для некоторого $$$1 \leq i \leq n$$$.
  2. $$$x = 2y + 1$$$ и $$$y$$$ находится в $$$S$$$.
  3. $$$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$$$.

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

Первая строка содержит два целых числа $$$n$$$ и $$$p$$$ $$$(1 \leq n, p \leq 2 \cdot 10^5)$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$.

Гарантируется, что все числа в $$$a$$$ различны.

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

Выведите единственное целое число — количество элементов в $$$S$$$, строго меньших $$$2^p$$$. Не забудьте вывести его по модулю $$$10^9 + 7$$$.

Примеры
Входные данные
2 4
6 1
Выходные данные
9
Входные данные
4 7
20 39 5 200
Выходные данные
14
Входные данные
2 200000
48763 1000000000
Выходные данные
448201910
Примечание

В первом примере элементы меньше $$$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\}$$$.