给定一个数组 $$$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\}$$$。