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:

$x = a_i$ for some $1 \leq i \leq n$.

$x = 2y + 1$ and $y$ is in $S$.

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

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

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


-----Examples-----

Input
2 4
6 1
Output
9
Input
4 7
20 39 5 200
Output
14
Input
2 200000
48763 1000000000
Output
448201910


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

Difficulty: MEDIUM_HARD
Tags: Bit manipulation

String algorithms

Number theory

Dynamic programming

Mathematics

Matrices
Skill types: Dynamic programming

Bit manipulation

Starter code:

Solutions:
import sys
from collections import Counter

def input():
	return sys.stdin.readline()[:-1]

def readline():
	return map(int, input().split())
MOD = 10 ** 9 + 7

def main():
	(n, p) = readline()
	a = sorted(readline())
	values = set()
	for ai in a:
		v = ai
		while v not in values:
			r = v % 4
			if r == 2 or v == 0:
				values.add(ai)
				break
			elif r == 0:
				v //= 4
			else:
				v //= 2
	c = Counter(map(int.bit_length, values))
	x = y = 0
	ans = 0
	for i in range(1, p + 1):
		z = (c.get(i, 0) + x + y) % MOD
		ans += z
		(x, y) = (y, z)
	print(ans % MOD)
main()


import sys
input = sys.stdin.readline

def solve(n, p, arr):
	m = 10 ** 9 + 7
	nums = set()
	candidate = []
	arr.sort()
	for num in arr:
		val = num
		while val > 1 and val not in nums:
			if val % 4 == 0:
				val //= 4
			elif val % 2 == 1:
				val //= 2
			else:
				break
		if val not in nums:
			candidate.append(num)
			nums.add(num)
	dp = [0] * p
	numCombs = [0] * p
	dp[-1] = 1
	numCombs[-1] = 1
	if p >= 2:
		dp[-2] = 2
		numCombs[-2] = 3
	idx = p - 3
	while idx > 0:
		dp[idx] = (dp[idx + 1] + dp[idx + 2]) % m
		numCombs[idx] = (dp[idx] + numCombs[idx + 1]) % m
		idx -= 1
	ans = 0
	for num in candidate:
		length = len(bin(num)[2:])
		if length > p:
			continue
		elif length == p:
			ans += 1
			ans %= m
		else:
			ans += numCombs[length] + 1
			ans %= m
	print(ans)
(n, p) = map(int, input().split())
arr = list(map(int, input().split()))
solve(n, p, arr)


import sys
from bisect import bisect

def input():
	return sys.stdin.readline()[:-1]

def readline():
	return map(int, input().split())
MOD = 10 ** 9 + 7

def main():
	(n, p) = readline()
	a = sorted(readline())
	c = [0] * 32
	for (i, ai) in enumerate(a):
		v = ai
		while True:
			b = bisect(a, v, lo=0, hi=i)
			if b > 0 and a[b - 1] == v:
				break
			r = v & 3
			if r == 2 or v < a[0]:
				c[ai.bit_length()] += 1
				break
			elif r == 0:
				v >>= 2
			else:
				v >>= 1
	x = y = 0
	ans = 0
	for i in range(1, p + 1):
		z = ((c[i] if i < 32 else 0) + x + y) % MOD
		ans += z
		(x, y) = (y, z)
	print(ans % MOD)
main()


(n, p) = map(int, input().split())
l = input().split()
l = [int(c) for c in l]
mod = 1000000007
Fib = [1, 1]
for i in range(p):
	Fib.append((Fib[-1] + Fib[-2]) % mod)
pref = [0]
for i in range(len(Fib)):
	pref.append((pref[-1] + Fib[i]) % mod)

def infS(k):
	u = k.bit_length()
	if u > p:
		return 0
	return pref[p - u + 1]
l.sort()
lset = set()
for v in l:
	u = v
	if u in lset:
		continue
	while u > 1 and u % 4 != 2:
		if u % 4 == 0:
			u //= 4
		else:
			u = (u - 1) // 2
		if u in lset:
			break
	else:
		lset.add(v)
l = list(lset)
res = 0
for k_ in l:
	res += infS(k_)
	res %= mod
print(res)


(n, p) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
usefulSeeds = {arr[0]}

def isUseful(n, S):
	while n:
		if n in S:
			return False
		elif n % 4 == 0:
			n /= 4
		elif n % 2 == 1:
			n -= 1
			n /= 2
		else:
			return True
	else:
		return True
for i in range(1, n):
	if isUseful(arr[i], usefulSeeds):
		usefulSeeds.add(arr[i])
from math import log2, floor
g = [0 for _ in range(35)]
for seed in usefulSeeds:
	k = floor(log2(seed))
	if k < p:
		g[k] += 1
dp = [0 for _ in range(p)]
rep = 0
mod = 10 ** 9 + 7
for i in range(p):
	if i < 35:
		dp[i] += g[i]
	if i >= 1:
		dp[i] += dp[i - 1]
		dp[i] = dp[i] % mod
	if i >= 2:
		dp[i] += dp[i - 2]
		dp[i] = dp[i] % mod
	rep += dp[i]
	rep = rep % mod
print(rep)


import math
(n, p) = [int(i) for i in input().strip().split()]
a = [int(i) for i in input().strip().split()]
mod = 1000000007
a.sort()
useful = set()
for i in range(n):
	x = a[i]
	flag = False
	while x > 0:
		if x in useful:
			flag = True
		if x & 1:
			x = x >> 1
		elif x & 3:
			break
		else:
			x = x >> 2
	if not flag:
		useful.add(a[i])
cnt = [0 for i in range(30)]
for x in useful:
	cnt[int(math.log2(x))] += 1
dp = [0 for i in range(p)]
ans = 0
for i in range(p):
	if i < 30:
		dp[i] = cnt[i]
	if i >= 1:
		dp[i] += dp[i - 1]
		if dp[i] >= mod:
			dp[i] -= mod
	if i >= 2:
		dp[i] += dp[i - 2]
		if dp[i] >= mod:
			dp[i] -= mod
	ans += dp[i]
	if ans >= mod:
		ans -= mod
print(ans)