시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 1 1 1 100.000%

문제

Seunghyun is a mathematician, and he likes good jokes. 

For a set $U = \{0, 1, \cdots, 2^k - 1\}$, a nonempty subset $A \subset U$ is good if it satisfies the following rules. 

  • For any $x, y \in S$, their bitwise-and $x \And y$ should be in $S$. 
  • For any $x, y \in S$, their bitwise-or $x \mid y$ should be in $S$. 

You are given $n$ distinct integers in $[0, 2^k-1]$ range. Find the number of good sets which contains all $n$ integers. 

입력

The first line contains two integers $k, n$. ($1 \le k \le 7, 0 \le n \le 2^k$)

The next line contains $n$ distinct integers $a_1, a_2, \cdots, a_n$($0 \le a_i \le 2^k - 1$).

출력

Print a single integer denoting the number of good sets.

예제 입력 1

2 1
0

예제 출력 1

7

예제 입력 2

4 3
1 2 7

예제 출력 2

29

출처

  • 문제를 만든 사람: ainta