def main():
MOD = int(1e9 + 7)
dp = [0] * 200005
dp[0] = 1
for i in range(1, 200005):
dp[i] += dp[i - 1]
if i - 2 >= 0:
dp[i] += dp[i - 2] dp[i] %= MOD
dps = dp.copy() for i in range(1, 200005):
dps[i] += dps[i - 1]
dps[i] %= MOD
n, p = readIntArr()
a = readIntArr()
a.sort()
allNums = set(a)
vi = [False] * n
for i, x in enumerate(a):
while x > 0 and (x % 2 == 1 or x % 4 == 0):
if x % 2 == 1: x //= 2
elif x % 4 == 0: x //= 4
if x in allNums: vi[i] = True
break
ans = 0
for i, x in enumerate(a):
if not vi[i]:
extraLength = p - x.bit_length()
if extraLength >= 0:
ans += dps[extraLength]
ans %= MOD
print(ans)
return
import sys
input=sys.stdin.buffer.readline
def oneLineArrayPrint(arr):
print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
def readIntArr():
return [int(x) for x in input().split()]
def makeArr(defaultValFactory,dimensionArr): dv=defaultValFactory;da=dimensionArr
if len(da)==1:return [dv() for _ in range(da[0])]
else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
def queryInteractive(a, b, c):
print('? {} {} {}'.format(a, b, c))
sys.stdout.flush()
return int(input())
def answerInteractive(x1, x2):
print('! {} {}'.format(x1, x2))
sys.stdout.flush()
inf=float('inf')
from math import gcd,floor,ceil
import math
for _abc in range(1):
main()#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long int
#define pb push_back
#define f(i, j, k) for (int i = j; i < k; i++)
#define rev(i, j, k) for (int i = j; i >= k; i--)
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define SET(x) cout << fixed << setprecision(x);
const int MOD = 1e9+7;
int ceil_div(int a, int b) { return (a + b - 1) / b; }
typedef vector<int> vi;
typedef vector<pair<int, int>> vp;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key
void solve()
{
int n,p;
cin>>n>>p;
vi a(n);
f(i,0,n)
{
cin>>a[i];
}
sort(all(a));
map<int,int>mp;
vi dp(p,0);
f(i,0,n)
{
int temp=a[i];
int f=0;
while(temp>0 && (temp%2==1 || temp%4==0))
{
if(temp%4==0)
{
temp/=4;
}
else if(temp%2==1)
{
temp/=2;
}
else
{
break;
}
if(mp[temp]==1)
{
f=1;
break;
}
}
if(f==0)
{
mp[a[i]]+=1;
int x=log2(a[i]);
if(x<p)
dp[x]+=1;
}
}
int ans=0;
f(i,0,p)
{
if(i>=1)
{
dp[i]+=dp[i-1];
dp[i]%=MOD;
}
if(i>=2)
{
dp[i]+=dp[i-2];
dp[i]%=MOD;
}
ans+=dp[i];
ans%=MOD;
}
cout<<ans<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tt = 1;
// cin >> tt;
f(i, 1, tt + 1)
{
solve();
}
return 0;
}289B - Polo the Penguin and Matrix | 1716A - 2-3 Moves |
1670B - Dorms War | 1716B - Permutation Chain |
987A - Infinity Gauntlet | 1676G - White-Black Balanced Subtrees |
1716D - Chip Move | 1352F - Binary String Reconstruction |
1487B - Cat Cycle | 1679C - Rooks Defenders |
56A - Bar | 1694B - Paranoid String |
35A - Shell Game | 1684A - Digit Minimization |
43B - Letter | 1017A - The Rank |
1698B - Rising Sand | 235A - LCM Challenge |
1075B - Taxi drivers and Lyft | 1562A - The Miracle and the Sleeper |
1216A - Prefixes | 1490C - Sum of Cubes |
868A - Bark to Unlock | 873B - Balanced Substring |
1401D - Maximum Distributed Tree | 1716C - Robot in a Hallway |
1688B - Patchouli's Magical Talisman | 99A - Help Far Away Kingdom |
622B - The Time | 1688C - Manipulating History |