Giải bài trực tuyến

English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/periodni

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