Cho một mảng gồm n phần tử A[1], A[2], …, A[n]. Các phần tử là các số nguyên trong nằm trong đoạn [0, m] với m là số cho trước. (1≤ n ≤10^5, 1≤ m ≤100)
Đếm số cách thay số 0 có trong mảng bằng các số nằm trong đoạn [1, m] sao cho chênh lệch tuyệt đối giữa hai giá trị liền kề nhiều nhất là 1.

Input

• Dòng đầu vào đầ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 A[1], A[2], …, A[n].

Output

• In một số nguyên: số lượng dãy chia lấy dư cho 10^9+7.

Example

3 5 
2 0 2

3

Scoring

• Subtask 1: 50% số test tương ứng với 50% số điểm chỉ có 1 số có giá trị bằng 0 trong dãy A.
• Subtask 2: 50% số test tương ứng với 50% số điểm không có ràng buộc gì thêm.