P1077 [NOIP 2012 Junior] Arranging Flowers

Xiaoming’s flower shop has just opened. To attract customers, he wants to place a row of $m$ pots of flowers at the entrance. Based on a survey, he listed the $n$ most popular types of flowers, numbered from $1$ to $n$. To showcase more types, it is required that for each type $i$, no more than $a_i$ pots are used. When arranging, flowers of the same type must be placed together, and different types must be placed in increasing order of their labels. Write a program to compute how many different arrangements there are.

The first line contains two positive integers $n$ and $m$, separated by a single space. The second line contains $n$ integers, separated by single spaces, representing $a_1, a_2, \cdots, a_n$.

Output a single integer, the number of arrangements. Note: since the number may be large, output the answer modulo $10^6 + 7$.

Constraints - For $20\%$ of the testdata: $0 < n \le 8$, $0 < m \le 8$, $0 \le a_i \le 8$. - For $50\%$ of the testdata: $0 < n \le 20$, $0 < m \le 20$, $0 \le a_i \le 20$. - For $100\%$ of the testdata: $0 < n \le 100$, $0 < m \le 100$, $0 \le a_i \le 100$. NOIP 2012 Junior Problem 3. Translated by ChatGPT 5