Infinite Set

题意翻译

给定一个长度为 $n$ 的数组 $a$。**保证数组 $a$ 中的所有元素互不相同**。 让我们规定一个无穷整数集合 $S$ 具有如下性质： - $\forall 1\leqslant i\leqslant n$，$a_i$ 一定在集合 $S$ 中。 - 如果 $x$ 在集合 $S$ 中，那么 $2x+1$ 和 $4x$ 也一定都在集合 $S$ 中。 请求出集合 $S$ 中**严格小于** $2^p$ 的数的个数。由于结果可能很大，你只需要输出其对 $10^9+7$ 取模之后的值。 数据范围： - $1\leqslant n,p\leqslant 2\times 10^5$。 - $1\leqslant a_i\leqslant 10^9$。 Translated by Eason_AC

题目描述

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

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

2 4
6 1

输出样例 #1

9

输入样例 #2

4 7
20 39 5 200

输出样例 #2

14

输入样例 #3

2 200000
48763 1000000000

输出样例 #3

448201910

说明

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