Luka is bored in chemistry class so he is staring at a large periodic table of chemical elements hanging from a wall above the blackboard. To kill time, Luka decided to make his own table completely different from the one in the classroom.

His table consists of \(N\) columns, each with some height, aligned at the bottom. After he draws the table he needs to fill it with elements. He first decided to enter the noble gases of which there are \(K\). Luka must put them in the table so that no two noble gases are close to each other.

Two squares in the table are close to each other if they are in the same column or row, and all squares between them exist.

Write a program that, given \(N\), \(K\) and the heights of the \(N\) columns, calculates the total number of ways for Luka to place the noble gases into the table. This number can be large, so output it modulo \(1\,000\,000\,007\).

In test cases worth 40% of points, all numbers in the input will be less than 15.
In test cases worth 70% of points, all numbers in the input will be less than 100.
Contest #4, \(17^{th}\) January 2009

The first line contains the integers \(N\) and \(K\) separated by a space (\(1 \le N \le 500\), \(1 \le K \le 500\)), the number of columns in Luka's table and the number of noble gases.

The next line contains \(N\) positive integers, separated by spaces. These are heights of the columns from left to right. The heights will be at most \(1\,000\,000\).

Output the number of ways for Luka to fill his table with noble gases, modulo \(1\,000\,000\,007\).

Scoring: In test cases worth \(40\%\) of points, all numbers in the input will be less than \(15\). In test cases worth \(70\%\) of points, all numbers in the input will be less than \(100\).

riseoj 작성

출처 COCI 2008/2009 Contest 4