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,\ldots,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 \leq n \leq 10^5\)
• \(1 \leq m \leq 100\)
• \(0 \leq x_i \leq m\)

Example

Sample input

3 5  
2 0 2

Sample output

3

Note

The arrays \([2,1,2]\), \([2,2,2]\) and \([2,3,2]\) match the description.