Description

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.

Input Format

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 Format

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

2 4
3 2

2

Hint

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