Description

Xiao Ming's flower shop has just opened, and to attract customers, he wants to display a row of flowers at the entrance, consisting of m pots in total. Through a survey of customer preferences, Xiao Ming has listed n types of flowers that customers like the most, labeled from 1 to n. To showcase a greater variety of flowers at the entrance, it is stipulated that the i-th type of flower cannot exceed a_i pots. When arranging the flowers, the same type of flower must be placed together, and different types of flowers must be arranged in ascending order of their labels. Write a program to calculate the total number of different flower arrangement schemes.

Input Format

The first line contains two positive integers n and m, separated by a space.

The second line contains n integers, separated by spaces, representing a_1, a_2, ..., a_n.

Output Format

Output consists of a single line with an integer, representing the number of possible schemes.

Note: Since the number of schemes may be very large, please output the result modulo 1000007.

```input1 2 4 3 2 ``` ```output1 2 ``` ## Hint

【Data Range】

For 20% of the data: 0 < n ≤ 8, 0 < m ≤ 8, 0 ≤ ai ≤ 8;

For 50% of the data: 0 < n ≤ 20, 0 < m ≤ 20, 0 ≤ ai ≤ 20;

For 100% of the data: 0 < n ≤ 100, 0 < m ≤ 100, 0 ≤ ai ≤ 100.

Source

NOIP2012-J3