题目描述

The following two steps, on an array $x$ consisting of positive integers, are called an operation:

• Select any two adjacent elements in $x$, decrease one of them by $1$, and set the other to $0$.
• Remove all zeros from $x$.

We call $x$ $\textit{mystic}$ if and only if it can be transformed into an empty sequence after a finite number of operations (possibly zero).

You are given an array $a$ consisting of $n$ integers, as well as an integer $m$. Each element of $a$ is either an integer from $1$ to $m$ or $-1$. Your task is to replace every occurrence of $-1$ in $a$ with any integer from $1$ to $m$.

Determine the number of distinct mystic arrays $a$ that can be obtained after the replacement. Since the answer can be very large, output it modulo $10^9 + 7$.

输入格式

The first line of the input contains two integers $n$ and $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^8$).

The second line of the input contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\le a_i \le m$ or $a_i=-1$).

输出格式

Output a single integer, representing the number of distinct mystic sequences $a$ that can be obtained, modulo $10^9 + 7$.

2 2
-1 -1

3

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

9125

提示

In the first test, the array $a$ is $[-1, -1]$. By replacing both $-1$-s, one possible result is $[1, 2]$. In this case, we select the two adjacent numbers: decrease the first by $1$ and set the second to $0$, obtaining $[0, 0]$. After removing all zeros, the sequence becomes empty. Hence, $[1, 2]$ is a mystic sequence.

Similarly, if we replace the $-1$-s with $[1, 1]$ or with $[2, 1]$, both sequences can also be reduced to empty. Therefore, the total number of distinct mystic sequences is $3$.