Cho một mảng gồm N số nguyên dương có giá trị các phần tử thuộc đoạn [1, M], và giá trị tuyệt đối của hiệu hai giá trị liền kề tối đa là 1.

Vì một số lỗi kỹ thuật, hệ thống đã làm đánh mất thông tin về giá trị của một số phần tử, và những vị trí bị mất thông tin đều có giá trị là 0, nhiệm vụ của bạn là đếm số lượng mảng có thể là mảng ban đầu chưa bị mất thông tin.

Input

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 cho mỗi giá trị (1 <= N <= 10^5, 1 <= M <= 100).
Dòng tiếp theo 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 giá trị chưa biết.

Output

In ra một số nguyên: số lượng mảng modulo 10^9 + 7.

Example

input
3 5
2 0 2

output
3

Note

Các mảng thỏa mãn ví dụ là [2, 1, 2], [2, 2, 2] và [2, 3, 2].