Mô tả dãy cảm biến

Bối cảnh và bài toán

Có dãy dài n, mỗi phần tử phải nằm trong 1..m và hai phần tử kề nhau chênh không quá 1. Một số vị trí đã biết, giá trị 0 nghĩa là chưa biết.

Yêu cầu

Đếm số dãy hoàn chỉnh hợp lệ modulo 10^9+7.

Input

Dòng 1 n m; dòng 2 gồm n số, 0 hoặc giá trị cố định.

Output

In số cách.

Ràng buộc

• 1 <= n <= 10^5
• 1 <= m <= 100

Chấm điểm

Ví dụ 1

Input

3 5
2 0 2

Output

3

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

1 3
0

Output

3

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Array Description. Bản FULLHOUSE DEV đã biên tập bối cảnh/format và ràng buộc khi cần để khớp scope-lock của khóa học.