Can You Count the Bit Strings?

Represent each given integer as exactly n bits (leading zeros allowed). For each original string, any zero bits may be flipped to 1; an original 1 cannot be changed to 0, and flipping nothing is also allowed. Find the size of the union of all results produced by all original strings; duplicate results are counted once, and no modulus is taken.

输入格式

The first line contains n k, and the second line contains k integers. This site adds 1≤n≤20, 1≤k≤100000, and 0≤integer<2ⁿ; the input may contain duplicates.

输出格式

Output the single integer required by the problem.

样例 1

输入：

3 2
1 2

输出：

6

样例 2

输入：

2 2
3 3

输出：

1

样例 3

输入：

4 2
0 15

输出：

16

样例说明

The answers to the three public examples are, in order: 6; 1; 16. The examples were checked by independent enumeration, state search, or direct simulation.