Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. AND Graph

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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:

Graph from second sample:

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/06/2020 13:01:50 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|