Victory Deck Order Count

After the midterm exam, Rokuka decides that mathematics is too boring and instead challenges Yuuta to a duel‐inspired card game. In her deck, there are a total of m+1 cards. The bottom card is fixed; therefore, we only consider the first m cards. Among these m cards, exactly n of them are special cards and the rest (m − n) are normal cards. Each special card has an associated integer value w_i (for 1 ≤ i ≤ n) that means that when the card is played, you immediately draw w_i cards from the deck. It is guaranteed that

[ \sum_{i=1}^{n} w_i = m, ]

so that if all special cards are played they exactly draw out all m cards.

The game proceeds as follows. At the beginning of the turn, you draw the top card from the deck into your hand. Then, you repeatedly play a card from your hand. If you play a special card with value w, you immediately draw w new cards from the deck; if you play a normal card (denoted by 0) nothing extra happens. The process continues until either you manage to draw the fixed bottom card (i.e. you have drawn all m cards from the top part, so that when drawing you obtain the final fixed card) and you win, or your hand becomes empty and you lose.

Note: Since the m cards (excluding the fixed bottom card) are randomly shuffled, there are exactly m! possible deck orders. Your task is to count in how many of these deck orders Rokuka can win the duel by drawing the bottom card in one turn using an optimal playing strategy.

Example 1: Consider m = 6 and n = 2 with special card values {4, 2}. (The remaining 4 cards are normal cards represented by 0.) One winning deck order is:

• Deck order (first m cards): {4, 0, 0, 2, 0, 0}.
• Play sequence: draw card 4; play it to draw the next 4 cards; then play the card 2 to draw 2 more cards – the fixed bottom card is then drawn and Rokuka wins.

Example 2: For the deck order {2, 0, 0, 4, 0, 0} (with the same parameters) Rokuka loses because after drawing the first card 2 and playing it (drawing 2 cards), the remaining special card 4 is not drawn in time.

Input/Output Note: It turns out that a deck order is winning if and only if, with an optimal strategy (i.e. always playing a special card if available), the first card drawn is a special card and the chain of extra draws is sufficient to eventually draw all m cards. One may show that the number of winning orders can be computed by the following idea:

Let the current "hand count" be f (initially f = 1 due to the first draw). When you choose to play a special card with value w from your hand, you pay a cost of 1 card (the card played) and then gain w cards (drawn immediately), so that your hand count becomes f − 1 + w. However, the deck order forces restrictions on when the special cards become available. In an optimal strategy the order in which you play the special cards can be rearranged arbitrarily among those drawn. For a given ordering τ of the n special cards, if you let

[ f(0)=1, \quad f(i)=f(i-1)-1+w_{\tau(i)} \quad (1 \le i \le n), ]

then a necessary and sufficient condition for winning is that when playing the special cards in the order τ, the special card played at step i must be drawn from the deck. Since drawing w_{\tau(i)} cards provides exactly f(i-1) possible places to “insert” the special card played at step i, the total number of winning orders can be computed by summing over all orders τ the product

[ \prod_{i=2}^{n} f(i-1) = \prod_{i=2}^{n} \Bigl(1+\sum_{j=1}^{i-1}(w_{\tau(j)}-1)\Bigr), ]

and then multiplying by the number of ways to order the normal cards, which is (m − n)!.

Your task is to compute the number of winning deck orders.

inputFormat

The first line contains two integers m and n (1 ≤ n ≤ m). The second line contains n positive integers w₁, w₂, ..., w_n such that \(\sum_{i=1}^{n} w_i = m\). These represent the values on the special cards. The deck consists of these n special cards and m − n normal cards (denoted by 0).

Note: If n = 0 (i.e. there are no special cards) the game is lost, and the answer is 0.

outputFormat

Output a single integer – the number of winning deck orders.

sample

6 2
4 2

144