Infinite Set
Contest: Codeforces Round 772 (Div. 2)
Difficulty rating: 1800
Tags: bitmasks, dp, math, matrices, number theory, strings

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$$$.

Input format:
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.

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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\}$$$.

Example input:
2 4
6 1

Example output:
9

Example input:
4 7
20 39 5 200

Example output:
14

Editorial:
First of all, let's discuss the problem where $$$n = 1$$$ and $$$a_1 = 1$$$.
For every integer $$$x$$$, there is exactly one integer $$$k$$$ satisfying $$$2^k \leq x < 2^{k + 1}$$$. Let's define $$$f(x) = k$$$.
Then, it's quite easy to find out $$$f(2x + 1) = f(x) + 1$$$ and $$$f(4x) = f(x) + 2$$$.
This observation leads to a simple dynamic programming solution: let $$$dp_i$$$ be the number of integer $$$x$$$ where $$$x \in S$$$ and $$$f(x) = i$$$. The base case is $$$dp_{0} = 1$$$ and the transition is $$$dp_i = dp_{i - 1} + dp_{i - 2}$$$.
After computing the $$$dp$$$ array, the final answer will be $$$\sum\limits_{i = 0}^{p - 1}dp_i$$$.
For the general version of the problem, in order not to compute the same number two or more times, we need to delete all "useless" numbers. A number $$$a_i$$$ is called useless if there exists an index $$$j$$$ such that $$$a_j$$$ can generate $$$a_i$$$ after a series of operations (setting $$$a_j$$$ to $$$2 a_j + 1$$$ or $$$4 a_j$$$). After the deletion, we can simply do the same thing above, only changing the transition a little bit: $$$dp_i = dp_{i - 1} + dp_{i - 2} + g(i)$$$, where $$$g(i)$$$ = number of $$$j$$$ satisfying $$$f(a_j) = i$$$.
The final problem is how to find all the useless numbers. For every integer $$$x$$$, there are at most $$$\mathcal{O}(logx)$$$ possible "parents" that can generate it. Also, such "parent" must be smaller than $$$x$$$.
So, let's sort the array in increasing order. Maintain all useful numbers in a set, and for each $$$a_i$$$, we will check whether its "parent" exists or not. Once we confirm that its parent doesn't exist, we will append it to the set of useful numbers. This works in $$$\mathcal{O}(nlognlogC)$$$.
Total Complexity: $$$\mathcal{O}(nlognlogC + p)$$$.