Flower Shop Arrangement

In this problem, Xiao Ming has just opened a flower shop and wants to display a row of m flower pots to attract customers. He has identified his customers' n favorite types of flowers, numbered from 1 to n. To display as many varieties as possible, for each type i the number of pots used cannot exceed a_i. When arranging the flowers, all pots of the same type must be placed together, and different types must be arranged in increasing order of their number.

Formally, you are given two integers m and n, and a sequence of n integers a_1, a_2, ..., a_n. Count the number of ways to choose nonnegative integers x_1, x_2, ..., x_n such that:

$$\begin{aligned} & x_1+x_2+\cdots+x_n = m,\\[5pt] & 0 \le x_i \le a_i \quad \text{for } i=1,2,\ldots,n. \end{aligned} $$

Each valid sequence corresponds to a distinct arrangement where the i-th flower type appears in a contiguous block (if x_i > 0) and the blocks appear in increasing order of their indices. Compute the total number of different arrangements.

inputFormat

The input consists of two lines:

1. The first line contains two integers m and n, where m is the total number of flower pots, and n is the number of flower types.
2. The second line contains n integers: a₁, a₂, ..., a_n, where a_i denotes the maximum number of pots for type i.

outputFormat

Output a single integer representing the number of different arrangements.

sample

5 2
3 4

3