CF1635D.Infinite Set

You are given an array $a$ consisting of $n$ distinct positive integers.

Let's consider an infinite integer set $S$ which contains all integers $x$ that satisfy at least one of the following conditions:

1. $x = a_i$ for some $1 \leq i \leq n$.
2. $x = 2y + 1$ and $y$ is in $S$.
3. $x = 4y$ and $y$ is in $S$.

For example, if $a = [1,2]$ then the $10$ smallest elements in $S$ will be ${1,2,3,4,5,7,8,9,11,12}$.

Find the number of elements in $S$ that are strictly smaller than $2^p$. Since this number may be too large, print it modulo $10^9 + 7$.

给你一个由 $n$ 个互不相同的正整数组成的数组 $a$。

考虑一个无限整数集合 $S$，它包含所有满足以下至少一个条件的整数 $x$：

1. $x = a_i$，其中 $1 \leq i \leq n$；
2. $x = 2y + 1$，且 $y \in S$；
3. $x = 4y$，且 $y \in S$。

例如，若 $a = [1,2]$，则 $S$ 中最小的 $10$ 个元素为 $\{1,2,3,4,5,7,8,9,11,12\}$。

求 $S$ 中严格小于 $2^p$ 的元素个数。由于该数可能过大，请输出其对 $10^9 + 7$ 取模的结果。

The first line contains two integers $n$ and $p$ $(1 \leq n, p \leq 2 \cdot 10^5)$.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ $(1 \leq a_i \leq 10^9)$.

It is guaranteed that all the numbers in $a$ are distinct.

第一行包含两个整数 $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$ 中的所有数互不相同。

Print a single integer, the number of elements in $S$ that are strictly smaller than $2^p$. Remember to print it modulo $10^9 + 7$.

输出一个整数，表示集合 $S$ 中严格小于 $2^p$ 的元素个数。注意：结果需对 $10^9 + 7$ 取模后输出。

In the first example, the elements smaller than $2^4$ are ${1, 3, 4, 6, 7, 9, 12, 13, 15}$.

In the second example, the elements smaller than $2^7$ are ${5,11,20,23,39,41,44,47,79,80,83,89,92,95}$.

在第一个例子中，小于 $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}$。