Description

对于一个由正整数组成的数组 $x$，定义以下两步操作为一次操作：

1. 选择 $x$ 中任意两个相邻的元素，将其中一个减去 $1$，并将另一个置为 $0$；
2. 从 $x$ 中移除所有的 $0$。

如果数组 $x$ 能够在有限次（可能为 $0$ 次）操作后被完全清空（即变为空序列），则称数组 $x$ 是 神秘的。

现给定一个长度为 $n$ 的整数数组 $a$，以及一个整数 $m$。数组 $a$ 中的每个元素要么是 $1$ 到 $m$ 之间的整数，要么是 $-1$。你的任务是将数组 $a$ 中所有的 $-1$ 替换为 $1$ 到 $m$ 之间的任意整数。

请计算经过替换后，能够成为神秘数组的不同数组 $a$ 的数量。由于答案可能非常大，请输出对 $10^9 + 7$ 取模的结果。

Input Format

输入的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10^6$，$1 \le m \le 10^8$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le m$ 或 $a_i = -1$）。

Output Format

输出一个整数，表示可以得到的不同神秘序列 $a$ 的数量，对 $10^9 + 7$ 取模。

2 2
-1 -1

3

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

9125

Hint

在第一个测试中，数组 $a = [-1, -1]$。将两个 $-1$ 替换后，其中一种可能是 $[1, 2]$。此时我们选择相邻的两个数：将第一个数减去 $1$，并将第二个数置为 $0$，得到 $[0, 0]$。移除所有的 $0$ 后，序列变为空，因此 $[1, 2]$ 是一个神秘数组。

同样地，如果将 $-1$ 替换为 $[1, 1]$ 或 $[2, 1]$，这两种序列也都可以被化简为空。因此，共有 $3$ 种不同的神秘序列。

翻译由 ChatGPT-5 完成