Periodic Table

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.

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.

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