Codeforces Round 772 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

dp

math

matrices

number theory

strings

*1800

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Infinite Set

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/01/2023 12:52:29 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|