不难想到，x有边连出的一定是 (2^n-1) ^ x 的一个子集，直接连子集复杂度是爆炸的。。。但是我们可以一个1一个1的消去，最后变成补集的一个子集。

    但是必须当且仅当 至少有一个 a 等于 x 的时候， 可以直接dfs(all ^ x) ,否则直接消1连边。。。

 

Discription

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

Note

Graph from first sample:

Graph from second sample:

 

#include
     
      #define ll long longusing namespace std;const int maxn=5000005;int ci[233],T,n,a[maxn],ans,all;bool v[maxn],isp[maxn];inline int read(){	int x=0; char ch=getchar();	for(;!isdigit(ch);ch=getchar());	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';	return x;}void dfs(int x){	if(v[x]) return;	v[x]=1;		if(isp[x]) dfs(all^x);		for(int i=0;i<=T;i++) if(ci[i]&x) dfs(x^ci[i]);}inline void solve(){	for(int i=1;i<=n;i++) if(!v[a[i]]){		ans++,v[a[i]]=1,dfs(all^a[i]);	}}int main(){	ci[0]=1;	for(int i=1;i<=22;i++) ci[i]=ci[i-1]<<1;		T=read(),n=read(),all=ci[T]-1;	for(int i=1;i<=n;i++) a[i]=read(),isp[a[i]]=1;		solve();		printf("%d\n",ans);	return 0;}