Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PERIODNI - Periodni

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274516/problem/M

{assign var="code" value="PERIODNI"} {if $par==""} {assign var=par value=$locale} {/if}

{if $par=="en"} {literal}

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 (see example below). 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. In the example below, the 'a' squares are not close, but the 'b' squares are.

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.

Input

The first line contains the integers N and K separated by a space (1 ≤ N ≤ 500, 1 ≤ K ≤ 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

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

Example

Input:
5 2
2 3 1 2 4

Output:
43

{/literal}{elseif ($par=="vn" || $par=="")}{literal}

Luka đang buồn chán trong lớp hóa học, vì thế cậu bắt đầu bằng bảng tuần hoàn lớn các nguyên tố hóa học được treo trên bức tường phía trên bảng đen. Để giết thời gian, Luka quyết định tự tao cho mình một bảng hoàn toàn khác so với chiếc bảng trong lớp.

Chiếc bảng của cậu có N cột, mỗi cột có một độ cao nào đó, sắp sao cho đáy thẳng hàng nhau (xem ví dụ phía dưới). Sau khi vẽ bảng, cậu cần phải điền các nguyên tố vào. Đầu tiên cậu quyết định điền K loại khí hiếm. Luka phải điền chúng vào bảng sao cho không có hai khí hiếm nào gần nhau.

Hai ôvuông trong bảng được gọi là gần nhau nếu chúng ở cùng cột hoặc hàng, và tồn tại các hình vuông ở giữa chúng. Trong ví dụ dưới đây, 2 hình vuông ghi chữ 'a' không gần nhau, còn 2 hình vuông ghi chữ 'b' là gần nhau.

Viết chương trình, cho N, K và độ cao của N cột, tính tổng số cách mà Luka có thể điền các khí hiếm vào bảng. Số này rất lớn nên chỉ cần in ra phần dư của nó khi chia cho 1 000 000 007.

Input

Dòng đầu tiên chứa các số nguyên N và K (1 ≤ N ≤ 500, 1 ≤ K ≤ 500), là số lượng cột trong bảng của Luka và số lượng khí hiếm.

Dòng tiếp theo chứa N số nguyên dương là độ cao của các cột theo thứ tự từ trái sang phải. Độ cao của các cột không quá 1 000 000.

Output

Ghi ra số lượng cách Luka có thể điền các khí hiếm vào bảng lấy phần dư khi chia cho 1 000 000 007.

Example

Input:
5 2
2 3 1 2 4

Output:
43

{/literal} {/if}


Được gửi lên bởi:Race with time
Ngày:2009-01-18
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO PERL6 PYPY RUST SED
Nguồn bài:COCI 2008/2009

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.