Coalitions

문제

There are $NN$ members in the parliament, and each one of them is a representative of one of the $KK$ 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}\backslash 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}\backslash frac\{N\}\{2\}$ members of the parliament.

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

입력

The first line of input contains $NN$, the number of seats in the parliament, and $KK$, the number of parties ($1\le N\le {10}^{18}1\; \backslash le\; N\; \backslash le\; 10^\{18\}$, $1\le K\le 361\; \backslash le\; K\; \backslash le\; 36$). The second line contains $KK$ integers $M_{1}M\_1$, $M_{2}M\_2$, $\dots \backslash ldots$, $M_{K}M\_K$ ($1\le M_i\le N1\; \backslash le\; M\_i\; \backslash le\; N$), where $M_{i}M\_i$ is the number of members of the parliament in the $ii$-th party. It is guaranteed that $M_1+M_2+\cdots +M_K=NM\_1\; +\; M\_2\; +\; \backslash cdots\; +\; M\_K\; =\; N$.

출력

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

14 5
6 2 1 4 1

4

8 8
1 1 1 1 1 1 1 1

56

101 6
34 25 19 12 10 1

5