PERIODNI - Periodni
Giới hạn- Thời gian: 0.996s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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
- Người up: racer
- Nguồn bài: COCI 2008/2009