Cho một mảng gồm ~n~ phần tử ~A_1, A_2, \dots, A_n~. Mỗi phần tử là một số nguyên thuộc đoạn ~[0, m]~, trong đó ~m~ là số cho trước ~(1 \le n \le 10^5, 1 \le m \le 100)~.

Hãy đếm số cách thay thế các phần tử có giá trị ~0~ trong mảng bằng các số thuộc đoạn ~[1, m]~ sao cho chênh lệch tuyệt đối giữa hai phần tử liền kề không vượt quá ~1~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, m~, lần lượt là kích thước mảng và giới hạn trên của mỗi giá trị;

• Dòng tiếp theo chứa ~n~ số nguyên ~A_1, A_2, \dots, A_n~ ~(0 \le A_i \le m)~.

Output

In ra số cách xây dựng mảng thỏa mãn yêu cầu, lấy phần dư theo ~10^9+7~.

Scoring

Sample Input 1

3 5
2 0 2

Sample Output 1

3

Notes

Có ba mảng thỏa mãn yêu cầu là ~[2, 1, 2]~, ~[2, 2, 2]~ và ~[2, 3, 2]~.