AND Graph

题意翻译

给定一个 $m$ 个整数的集合,每个整数在 $0$ 到 $2^n-1$ 之间,以每一个整数作为顶点建无向图,当两个点 $x$ 和 $y$ 做与运算值为 $0$ 时,则认为 $x$ 和 $y$ 是连通的,即 $x$ 和 $y$ 之间有一条无向边。请求出图中连通块的个数。 **【输入格式】** 第一行输入两个整数 $n$ 和 $m$($0 \leq n\leq22$,$1 \leq m\leq2^n$)。 第二行输入 $m$ 个整数,即集合里的元素。 **【输出格式】** 一个整数,表示图中连通块的个数。

题目描述

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](https://en.wikipedia.org/wiki/Bitwise_operation#AND). Count the number of connected components in that graph.

输入输出格式

输入格式


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.

输出格式


Print the number of connected components.

输入输出样例

输入样例 #1

2 3
1 2 3

输出样例 #1

2

输入样例 #2

5 5
5 19 10 20 12

输出样例 #2

2

说明

Graph from first sample: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF986C/e7573a95a1389022471f615fc286ee6a456a86b7.png) Graph from second sample: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF986C/f997c124f5bc2f31b98c263f4d64a7c7ae66176f.png)