Respect
本题没有可用的提交语言。
Description
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\}$.
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 a single integer, the total number of subsets of $A$ that are respectable with respect to $n$.
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$.
7 5
1 2 3 5 6
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$.