Bài toán: Đếm số mảng hợp lệ

Đề bài

Cho một mảng có ~ n ~ phần tử trong khoảng từ ~ 1 ~ đến ~ m ~, với điều kiện độ chênh lệch tuyệt đối giữa hai phần tử liền kề không vượt quá 1. Một số phần tử trong mảng có thể chưa biết và được biểu diễn bởi số ~ 0 ~.

Nhiệm vụ của bạn là đếm số lượng mảng có thể tạo ra theo mô tả trên. Kết quả cần lấy modulo ~ 10^9 + 7 ~.

Input

• Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ m ~:
  • ~ n ~: độ dài của mảng.
  • ~ m ~: giá trị tối đa của các phần tử trong mảng.
• Dòng thứ hai chứa ~ n ~ số nguyên ~ x_1, x_2, \ldots, x_n ~:
  • ~ x_i = 0 ~: phần tử ~ i ~ chưa biết.
  • ~ x_i > 0 ~: phần tử ~ i ~ đã biết.

Output

• In ra một số nguyên: số lượng mảng hợp lệ (modulo ~ 10^9 + 7 ~).

Ràng buộc

• ~ 1 \leq n \leq 10^5 ~
• ~ 1 \leq m \leq 100 ~
• ~ 0 \leq x_i \leq m ~

Ví dụ

Input:

3 5
2 0 2

Output:

3

Giải thích:

• Các mảng hợp lệ là:
  • ~ [2, 1, 2] ~
  • ~ [2, 2, 2] ~
  • ~ [2, 3, 2] ~