← 返回题目列表

Codeforces · 1635/D

D. 无限集

中文机器翻译题面 查看原题

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

让我们考虑一个无限整数集 $$$S$$$,其中包含至少满足以下条件之一的所有整数 $$$x$$$:

1. 对于$$$1 \leq i \leq n$$$,$$$x = a_i$$$。
2. $$$x = 2y + 1$$$ 且 $$$y$$$ 位于 $$$S$$$ 中。
3. $$$x = 4y$$$ 且 $$$y$$$ 位于 $$$S$$$ 中。

例如,如果 $$$a = [1,2]$$$,则 $$$S$$$ 中的 $$$10$$$ 最小元素将为 $$$\{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$$$ 为模来打印它。

示例

输入 #1

2 4
6 1

输出 #1

9

输入 #2

4 7
20 39 5 200

输出 #2

14

输入 #3

2 200000
48763 1000000000

输出 #3

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