Periodic Table

Time limit1sMemory limit128 MB

Summary

Count ways to place K non-attacking pieces on a histogram-shaped grid where two cells in the same row are close only if all columns between them reach that row, modulo 1e9+7.

Level: Hard8 of 10
Topics: Dynamic programming, Stack, Combinatorics
Solved: No attempts yet

Problem

In a dream, Donghyuk sees an empty periodic table made of N columns. The i-th column has height h_i, and all columns are aligned at the bottom. No cell contains an element yet.

Donghyuk wants to place K noble gases in K distinct cells so that no two chosen cells are close to each other.

Two cells are close if they are in the same row or in the same column and there is no missing cell between them. Therefore, two cells in the same column can never both be chosen. In the same row, two cells cannot both be chosen if every column between them reaches that row. In the figure below, the two cells marked a are not close, while the two cells marked b are close.

Given N, K, and the heights of the N columns, compute the number of ways to place the K noble gases.

Input

The first line contains N and K. (1 <= N <= 500, 1 <= K <= 500)

The second line contains the heights h_1, h_2, ..., h_N of the N columns from left to right, separated by spaces. Each height is between 1 and 1,000,000, inclusive.

Output

Print the number of ways to place K noble gases, modulo 1,000,000,007.

Examples4

Example 1
Input
```
3 3
2 1 3
```
Expected output
```
2
```
Example 2
Input
```
4 1
1 2 3 4
```
Expected output
```
10
```
Example 3
Input
```
5 2
2 3 1 2 4
```
Expected output
```
43
```
Example 4
Input
```
3 2
999999 999999 999999
```
Expected output
```
990979013
```