Non‐Adjacent Rook Placement on a Jagged Table

Consider a table with n columns, where each column is bottom‐aligned. In other words, every column has a specified height, and the bottom cells of all columns form a complete row; however, the upper part of the table may be "jagged" (i.e. some columns are shorter than others).

You are given an integer k. You need to place k identical numbers into some cells of the table. The placement must obey the following rule:

Rule: In any two cells that are consecutive in a horizontal segment (i.e. in two adjacent columns which both contain that row), at most one cell may contain a number.

In other words, if two numbers are placed in adjacent columns and they lie in the same row (i.e. the row exists in both columns), then that is not allowed. Note that if there is a gap between numbers in the same horizontal row (because the cell is missing in an intermediate column), they are not considered to be in the same contiguous horizontal segment, and such placement is allowed.

Your task is to count the total number of valid placements modulo \(10^9+7\).

For example, in the figure, the placement marked with b is invalid because two numbers appear in the same column, while the placement marked with a is valid even though the numbers lie in the same row, because they are separated by a gap.

Note: The rule essentially forbids placing numbers in two adjacent columns in the same row if that row exists in both columns.

inputFormat

The input consists of two lines:

1. The first line contains two integers \(n\) and \(k\) (1 ≤ n ≤ 500, 0 ≤ k ≤ n), where \(n\) is the number of columns and \(k\) is the number of numbers to place.
2. The second line contains \(n\) integers \(h_1, h_2, \ldots, h_n\) (1 ≤ h_i ≤ 500) representing the height of each column.

You may assume that the table is given in left-to-right order.

outputFormat

Output a single integer: the number of valid placements modulo \(10^9+7\).

sample

2 1
3 2

5