Problem Description

Timothy is the on-site commander of a demolition company. Currently, there is a row of $n$ aging large oil tanks that are moving closer together, each containing a different amount of waste oil (a positive integer $x_i$).

Since the oil tanks were adjacent, Timothy decided to adopt a "spark ignition chain" approach to save on demolition costs:

1. Choose two adjacent oil tanks $A$ and $B$.
2. Extract $1$ liter of waste oil from $A$ as fuel, and use the heat generated by the blowtorch to directly vaporize and burn all the waste oil in the adjacent tank $B$.
3. After tank $B$ is emptied, the construction team will quickly hoist it away. At this time, the tanks originally located on both sides of $B$ will automatically move closer and become adjacent.
4. If $A$ is also fully utilized at this point, the construction team will promptly remove it. At this time, the oil tanks originally located on both sides of $A$ will automatically move closer together, becoming adjacent.

If all the oil tanks in this row can be emptied (removed) through this method, we call this sequence of oil tanks "completely removable".

There are $n$ numbered oil tank positions on site, and the oil volume $a_i$ of some oil tanks is known. Positions marked with $-1$ indicate that the oil tank label is damaged, but it is known that their maximum capacity is $m$ liters (i.e., the oil volume is between $1$ and $m$). Now, please calculate: among all the possible capacities filled in the positions where the labels are damaged, how many different combinations of oil volumes can make the construction team successfully empty the row of oil tanks?

Input

The first line contains two integers $n$ and $m$ satisfying ($2 \leqslant n \leqslant 10^6$, $1 \leqslant m \leqslant 10^8$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ satisfying ($1 \leqslant a_i \leqslant m$ or $a_i = -1$).

Output

Output an integer representing the total number of fuel combinations that can be successfully emptied, modulo $10^9 + 7$.

Samples

2 2
-1 -1

3

6 10
-1 -1 -1 -1 1 7

9125

Note

In the first set of test cases, the array $a = [-1, -1]$. After replacing the two unknown oil tanks with $-1$, one possible outcome is $[1, 2]$. At this point, we select two adjacent oil tanks: subtract $1$ from the first tank's oil volume and burn the second tank, resulting in $[0, 0]$. After removing all empty oil tanks, the clearance is successfully completed, so $[1, 2]$ is a possible scenario.

Similarly, if the unknown oil tank $-1$ is replaced with either $[1, 1]$ or $[2, 1]$, both of these two oil tanks can be emptied. Therefore, there are a total of $3$ different possible scenarios.