You know that an array has ~n~ integers between ~1~ and ~m~, and the absolute difference between two adjacent values is at most ~1~.

Given a description of the array where some values may be unknown, your task is to count the number of arrays that match the description.

Input Specification

• The first input line has two integers ~n~ and ~m~: the array size and the upper bound for each value.
• The next line has ~n~ integers ~x_1, x_2, \dots, x_n~: the contents of the array. Value ~0~ denotes an unknown value.

Output Specification

• Print one integer: the number of arrays modulo ~10^9 + 7~.

Constrains

• ~1 \le n \le 10^5~
• ~1 \le m \le 100~
• ~0 \le x_i \le m~

Sample Cases

Input #1:

3 5
2 0 2

Output #1:

3

Explanation #1:

• The arrays ~[2,1,2]~, ~[2,2,2]~ and ~[2,3,2]~ match the description.