Mô tả mảng

Trong một chuyến công tác tại Mỹ, FullHouse Dev được giao một bài toán thú vị về xử lý mảng. Họ cần phải đếm số lượng mảng thỏa mãn một số điều kiện đặc biệt.

Bài toán

FullHouse Dev được cung cấp một mảng có \(n\) số nguyên, mỗi số có giá trị từ \(1\) đến \(m\). Đặc biệt, hiệu tuyệt đối giữa hai phần tử liền kề không được vượt quá \(1\). Một số vị trí trong mảng có thể chưa biết giá trị (được đánh dấu bằng số \(0\)). Nhiệm vụ của nhóm là đếm số lượng mảng khác nhau thỏa mãn mô tả trên.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): kích thước mảng và giới hạn trên của mỗi giá trị.
• Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2, ..., x_n\): nội dung của mảng. Giá trị \(0\) biểu thị một vị trí chưa biết giá trị.

OUTPUT FORMAT:

• In ra một số nguyên: số lượng mảng có thể có, lấy phần dư khi chia cho \(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ó ba mảng thỏa mãn điều kiện: [2,1,2], [2,2,2] và [2,3,2]. Các mảng này đều có hiệu tuyệt đối giữa hai phần tử liền kề không vượt quá 1 và các giá trị đều nằm trong khoảng từ 1 đến 5.