You are given a set of size mm with integer elements between 00 and 2n−12n−1 inclusive. Let's build an undirected graph on these integers in the following way: connect two integers xx and yy with an edge if and only if x&y=0x&y=0. Here && is the bitwise AND operation. Count the number of connected components in that graph.

Input

In the first line of input there are two integers nn and mm (0≤n≤220≤n≤22, 1≤m≤2n1≤m≤2n).

In the second line there are mm integers a1,a2,…,ama1,a2,…,am (0≤ai<2n0≤ai<2n) — the elements of the set. All aiai are distinct.

Output

Print the number of connected components.

Examples

Input

2 3
1 2 3

Output

2

Input

5 5
5 19 10 20 12

Output

2

题意：每个数当成一个点，对于任意两点，若x&y==0，则x和y连一条边。最后求图中有几个联通块。

分析：显然与二进制关系很大，找二进制联系是难点。假设x(2)=001001100,x&y=0则y=_ _0_ _00_ _即x中为1的位置y中都为0，x中为0的y中01都可以。如果做一下z=x^111111111，即z=110110011，这样的话，z以及z的所有“子集”都可以与x连一条边，这个子集是说z中任意多个1换成0后的数，如何枚举子集呢？添加一个判重数组，写个循环把z的每个1换成0得到z’，再继续递归，以同样的方法把z’的每个1换成0，这样不重不漏地枚举完所有可以与x相连的数字。并且对于每个z，z’及其子集们，如果发现有题中的其他数，那么再以同样的方法枚举与其相连的集合。因此一次dfs可以找出完整的一个连通分量。

#include<bits/stdc++.h>
using namespace std;
#define all_bits ((1<<n)-1)

int n,m,a[1<<23],cnt;
bool have[1<<23],vis[1<<23];

void dfs(int x)//x及x的子集均可被点连 
{
	if(vis[x])return;
	vis[x]=1;
	if(have[x])dfs(x^all_bits);
	for(int i=0;i<n;i++)
	{
		if(1<<i & x)dfs(x ^ 1<<i);
	}
}

int main()
{
	//freopen("input.in","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i];
		have[a[i]]=1;
	}
	for(int i=1;i<=m;i++)
	{
		if(!vis[a[i]])
		{
			cnt++;
			vis[a[i]]=1;
			dfs(a[i]^all_bits);
		}
	}
	cout<<cnt<<endl;
	return 0;
}