G. Respect
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let us call a subset $$$S$$$ of $$$\{1,2,\ldots,n\}$$$ respectable with respect to $$$n$$$ if:

  • there is a way to assign $$$+$$$ and $$$-$$$ signs to each element of $$$S$$$ so that the their total sum is divisible by $$$n$$$;
  • no non-empty proper subset of $$$S$$$ is respectable with respect to $$$n$$$.

You are given $$$n$$$ and a subset $$$A$$$ of $$$\{1,2,\ldots,n\}$$$. Your task is to find the total number of subsets of $$$A$$$ that are respectable with respect to $$$n$$$.

For example, if $$$n = 7$$$ and $$$A = \{1,2,3,5,6\}$$$, the subset $$$\{2,3,5\}$$$ is respectable, as $$$+2+3-5 = 0$$$ is divisible by $$$7$$$. The subset $$$\{1,6\}$$$ is also respectable, as $$$+1+6=7$$$ is also divisible by $$$7$$$. On the other hand, the subset $$$\{1,2,3,6\}$$$ is not respectable, as even though $$$+1+2+3-6 = 0$$$ is divisible by $$$7$$$, it contains the proper respectable subset $$$\{1,6\}$$$.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq m \leq n \leq 40$$$), where $$$m$$$ is the size of $$$A$$$. The next line contains $$$m$$$ distinct integers $$$a_1$$$, $$$\ldots$$$, $$$a_m$$$ ($$$1 \leq a_i \leq n$$$), the elements of $$$A$$$.

Output

Output a single integer, the total number of subsets of $$$A$$$ that are respectable with respect to $$$n$$$.

Example
Input
7 5
1 2 3 5 6
Output
6
Note

A set $$$P$$$ is called a proper subset of $$$S$$$ if it is a subset of $$$S$$$ and is not equal to $$$S$$$.