Infinite Set solution codeforces

Infinite Set solution codeforces

 

You are given an array aa consisting of nn distinct positive integers.

Let’s consider an infinite integer set SS which contains all integers xx that satisfy at least one of the following conditions:

  1. x=aix=ai for some 1in1≤i≤n.
  2. x=2y+1x=2y+1 and yy is in SS.
  3. x=4yx=4y and yy is in SS.

For example, if a=[1,2]a=[1,2] then the 1010 smallest elements in SS will be {1,2,3,4,5,7,8,9,11,12}{1,2,3,4,5,7,8,9,11,12}.

Find the number of elements in SS that are strictly smaller than 2p2p. Since this number may be too large, print it modulo 109+7109+7.

Input

The first line contains two integers nn and pp (1n,p2105)(1≤n,p≤2⋅105).

The second line contains nn integers a1,a2,,ana1,a2,…,an (1ai109)(1≤ai≤109).

It is guaranteed that all the numbers in aa are distinct.

Output

Print a single integer, the number of elements in SS that are strictly smaller than 2p2p. Remember to print it modulo 109+7109+7.

Examples
input

Copy
2 4
6 1
output

Copy
9
input

Copy
4 7
20 39 5 200
output

Copy
14
input

Copy
2 200000
48763 1000000000
output

Copy
448201910
Note

In the first example, the elements smaller than 2424 are {1,3,4,6,7,9,12,13,15}{1,3,4,6,7,9,12,13,15}.

In the second example, the elements smaller than 2727 are {5,11,20,23,39,41,44,47,79,80,83,89,92,95}{5,11,20,23,39,41,44,47,79,80,83,89,92,95}.

Leave a Comment

Your email address will not be published.