Ski Racing#741
The International Ski Federation is continuously working to increase the appeal of ski racing. In recent years, many disciplines have been created and tested – sprint races, mass starts, ski exchange races, and so forth. Many of these were already featured at the Vancouver Olympics. An essential aspect of increasing excitement is enhancing direct competition on the course, as happens in sprint races and mass starts. For these kinds of races, the organization of the start, especially athlete placement, is very important.
At an upcoming Winter Olympics, a new scheme for positioning athletes on the starting field has been proposed. As before, skiers are placed in several columns along the start line. Now, however, the number of participants in each column is determined by the competition rules. Additionally, skiers from the same country are subject to the following restrictions:
They cannot be placed in the same column.
They cannot be placed in the same row if all the positions between them in that row are occupied by other skiers (or if they are in adjacent columns). If at least one spot between them is empty, they may be placed in the same row.
The Ski Federation asks you to write a program that determines in how many ways athletes from one country can be positioned at the start.
The first line contains the integers and (1 \leq N, K \leq 400). The second line contains positive integers separated by spaces, describing the start columns. The -th number indicates the number of people in the -th column. Numbers do not exceed .
Print a single integer – the number of ways. Output the number modulo 10^9+7.
Example 1