Coalitions

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.