P14459 [ICPC 2025 Xi'an R] Mystique as Iris

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$.

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$.