Cho trước một mảng độ dài \(n\) trong đó có một số vị trí chưa được xác định giá trị. Hãy đếm số cách điền giá trị vào những vị trí đó thoả mãn điều kiện sau:

• Các giá trị trong mảng là số nguyên trong khoảng từ \(1\) đến \(m\)
• Chênh lệch giữa hai phần tử liền kề không quá \(1\)

Input

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

Output

• In một số nguyên: số lượng dãy (cũng là số lượng cách điền) chia lấy dư cho \(10 ^ 9 + 7\).

Constraints

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

Example

Sample input

3 5
2 0 2

Sample output

3

Note

Các dãy \([2, 1, 2]\), \([2, 2, 2]\), \([2, 3, 2]\) khớp với mô tả.