无限集合

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

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

定义一个无限整数集合 $S$。一个整数 $x$ 属于 $S$，当且仅当它满足下列至少一个条件：

1. 存在 $1\le i\le n$，使得 $x=a_i$；
2. 存在 $y\in S$，使得 $x=2y+1$；
3. 存在 $y\in S$，使得 $x=4y$。

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

请计算 $S$ 中严格小于 $2^p$ 的元素个数，并对 $10^9+7$ 取模。

输入格式

第一行包含两个整数 $n$ 和 $p$（$1\le n,p\le2\times10^5$）。

第二行包含 $n$ 个互不相同的整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le10^9$）。

输出格式

输出一个整数，表示 $S$ 中严格小于 $2^p$ 的元素个数对 $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

数据范围

对于所有测试数据，$1\le n,p\le2\times10^5$，$1\le a_i\le10^9$，且所有 $a_i$ 互不相同。

提示

第一个样例中，严格小于 $2^4$ 的元素为 $\{1,3,4,6,7,9,12,13,15\}$。