You are given a set of size $m$ with integer elements between $0$ and $2^{n}-1$ inclusive. Let's build an undirected graph on these integers in the following way: connect two integers $x$ and $y$ with an edge if and only if $x \& 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 $n$ and $m$ ($0 \le n \le 22$, $1 \le m \le 2^{n}$).

In the second line there are $m$ integers $a_1, a_2, \ldots, a_m$ ($0 \le a_{i} < 2^{n}$) — the elements of the set. All $a_{i}$ 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:

$0$

Graph from second sample:

[Image]

Source: codeforces | Difficulty: VERY_HARD
Tags: Spanning trees

Bit manipulation

Graph algorithms

Graph traversal


Solutions:
(n, m) = map(int, input().split())
a = set(map(int, input().split()))
y = 2 ** n
mk = [0] * (2 * y)
cur = 0
for x in a:
	if mk[x]:
		continue
	mk[x] = 1
	st = [x]
	while st:
		u = st.pop()
		if u < y:
			if not mk[y + u]:
				mk[y + u] = 1
				st.append(y + u)
		else:
			for b in range(n):
				v = u | 1 << b
				if u < v and (not mk[v]):
					mk[v] = 1
					st.append(v)
			v = y - 1 - (u - y)
			if v in a and (not mk[v]):
				mk[v] = 1
				st.append(v)
	cur += 1
print(cur)


import sys
inp = list(map(int, sys.stdin.buffer.read().split()))
(n, m) = inp[:2]
a = set(inp[2:])
y = 2 ** n
mk = [0] * (2 * y)
cur = 0
for x in a:
	if mk[x]:
		continue
	mk[x] = 1
	st = [x]

	def push(v):
		if not mk[v]:
			mk[v] = 1
			st.append(v)
	while st:
		u = st.pop()
		if u < y:
			push(y + u)
		else:
			for b in range(n):
				v = u | 1 << b
				push(v)
			v = y - 1 - (u - y)
			if v in a:
				push(v)
	cur += 1
print(cur)