题目描述

Timothy 是一家拆除公司的现场指挥官。现在有一排 $n$ 个相互靠拢的老旧大型油罐，每个油罐里残留着不同升数的废油（正整数 $x_i$）。

由于油罐紧挨着，为了节省拆除成本，Timothy 决定采用一种“引燃连锁”方案：

1. 选择两个相邻的油罐 $A$ 和 $B$。
2. 从 $A$ 中抽取 $1$ 升废油作为燃料，利用喷灯产生的热量直接气化并烧尽相邻油罐 $B$ 里的所有废油。
3. 油罐 $B$ 烧空后，施工队会迅速将其吊走。此时，原本位于 $B$ 左右两侧的油罐会自动靠拢，变为相邻。
4. 如果此时 $A$ 也被使用完毕，施工队也会迅速将其吊走。此时，原本位于 $A$ 左右两侧的油罐会自动靠拢，变为相邻。

如果这排油罐能通过这种的方式最终全部被清空（移除），我们称这组油罐序列是“可完全拆除的”。

现场有 $n$ 个编号的油罐位置，有些油罐的油量 $a_i$ 是已知的。而标记为 $-1$ 的位置表示油罐标签损毁，但已知其容量上限为 $m$ 升（即油量在 $1$ 到 $m$ 之间）。现请你计算：在所有标签损毁的位置中所填充的可能的容量中，有多少种不同的油量组合，能让这排油罐被施工队顺利清空？

输入描述

第一行包含两个整数 $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$）。

输出描述

输出一个整数，可以顺利清空的油量组合总数，对 $10^9 + 7$ 取模。

样例

样例 1

2 2
-1 -1

3

样例 2

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

9125

注释

在第一组测试用例中，数组 $a = [-1, -1]$。将两个未知的油罐 $-1$ 替换后，其中一种可能是 $[1, 2]$。此时我们选择相邻的两个油罐：将第一个油罐的油量减去 $1$，并将第二个油罐烧掉，得到 $[0, 0]$。移除所有的空油罐后完成顺利清空，因此 $[1, 2]$ 是一个可能的情况。

同样地，如果将未知的油罐 $-1$ 替换为 $[1, 1]$ 或 $[2, 1]$，这两桶油罐均能清空。因此，共有 $3$ 种不同的可能情况。