Ski Racing
The International Ski Federation is continuously striving to enhance the excitement of ski races. Over recent years, various disciplines have been developed and tested, including sprint races, mass starts, and ski change races. Many of these were showcased at the Vancouver Olympics. A key aspect of increasing excitement is boosting direct competition on the track, as seen in sprints and mass starts. In such races, the starting arrangement of athletes is crucial.
For the Sochi Olympics, a new method for positioning athletes on the starting field was proposed. As before, skiers are arranged in several columns along the starting line. However, the number of participants in each column is now specified by the competition rules. Additionally, skiers from the same country must adhere to the following restrictions:
They cannot be placed in the same column.
They cannot be in the same row if the entire section of the row between them is filled by other skiers (or if they are in adjacent columns). If there is at least one empty spot, they can be placed in the same row.
The Ski Federation requests you to develop a program that calculates the number of ways K athletes from one country can be arranged at the start.
Input
The first line contains the integers N and K (1 ≤ N, K ≤ 400). The second line provides N positive integers separated by spaces, describing the starting columns. The i-th number indicates the number of people in the i-th column. These numbers do not exceed 1000000.
Output
Output a single number representing the number of ways, modulo 10^9+7.