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

• 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

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

Constraints

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

Example Input

3 5
2 0 2

Example Output

3

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