시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB111100.000%

문제

There are $N$ members in the parliament, and each one of them is a representative of one of the $K$ parties. Now the parties have to form a ruling colation.

For a coalition to be able to rule, it needs a majority in the parliament. On the other hand, the more parties in the coalition, the less stable it is because of possible differences of opinion. Thus, a coalition that would still have a majority in the parliament after excluding some of the parties in it is not very sensible.

More precisely, a group of parties can form a stable coalition under two conditions:

  1. Together, the parties in the coalition have more than $\frac{N}{2}$ members of the parliament.
  2. If any of the parties were excluded from the coalition, the remaining ones would no longer have more than $\frac{N}{2}$ members of the parliament.

Count the number of possible groups that could form stable coalitions.

입력

The first line of input contains $N$, the number of seats in the parliament, and $K$, the number of parties ($1 \le N \le 10^{18}$, $1 \le K \le 36$). The second line contains $K$ integers $M_1$, $M_2$, $\ldots$, $M_K$ ($1 \le M_i \le N$), where $M_i$ is the number of members of the parliament in the $i$-th party. It is guaranteed that $M_1 + M_2 + \cdots + M_K = N$.

출력

The only line of output should contain a single integer: the number of possible stable coalitions.

예제 입력 1

14 5
6 2 1 4 1

예제 출력 1

4

Let's denote the parties as $a$, $b$, $c$, $d$, $e$ from left to right. Then the possible stable coalitions are: $$\begin{equation*} \{a, b\}, \qquad \{a, d\}, \qquad \{a, c, e\}, \qquad \{b, c, d, e\}. \end{equation*}$$ The group $\{a, c\}$ can't be a coalition, because they do not have more than $\frac{N}{2} = 7$ members of parliament in total. The group $\{a, b, c\}$ can't be a stable coalition, because after excluding $c$ it becomes $\{a, b\}$, which still has majority in the parliament.

예제 입력 2

8 8
1 1 1 1 1 1 1 1

예제 출력 2

56

Any group of 5 parties can form a stable coalition, so the answer is $C^5_8 = 56$.

예제 입력 3

101 6
34 25 19 12 10 1

예제 출력 3

5