Mô tả mảng (Array Description)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng độ dài $n$. Mỗi phần tử bằng $0$ nghĩa là chưa xác định, hoặc là một số trong $[1,m]$. Cần thay mọi số $0$ sao cho hai phần tử kề nhau chênh lệch không quá $1$. Hãy đếm số mảng hợp lệ.

Input

Dòng đầu chứa $n,m$. Dòng hai chứa $n$ số.

Output

In số cách modulo $10^9+7$.

Subtask

• Subtask 1 — 20 điểm: dữ liệu nhỏ, phù hợp để kiểm tra cách trực tiếp hoặc DP cơ bản.
• Subtask 2 — 30 điểm: dữ liệu trung bình, yêu cầu lưu trạng thái hợp lý.
• Subtask 3 — 50 điểm: toàn bộ giới hạn của gói Phước Hưng OJ.

Ví dụ

Input

3 5
2 0 2

Output

3

Giải thích

Kết quả được tính đúng theo quy tắc của đề. Đây là một trường hợp nhỏ để đối chiếu định dạng vào/ra trước khi nộp bài.