G. Good Set
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Seunghyun is a mathematician, and he likes good jokes.

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

  • for any , their bitwise-and should be in S.
  • for any , their bitwise-or should be in S.

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

Input

The first line contains two integers k, n. (1 ≤ k ≤ 7, 0 ≤ n ≤ 2k)

The next line contains n distinct integers a1, a2, ..., an(0 ≤ ai ≤ 2k - 1).

Output

Print a single integer denoting the number of good sets.

Examples
Input
2 1
0
Output
7
Input
4 3
1 2 7
Output
29