#P18049. Mystique as Iris

Mystique as Iris

Mystique as Iris

对于一个由正整数构成的序列,可以执行以下操作:

  1. 选择序列中两个相邻元素,将其中一个减去 11,将另一个变为 00。
  2. 删除序列中的所有 00,其余元素按原有相对顺序组成新序列。

若一个序列可以经过有限次上述操作变成空序列,则称其为神秘序列。允许执行零次操作。

给定长度为 nn 的数组 aa 和正整数 mm。数组中的每个元素或者是 [1,m][1,m] 内的整数,或者是 −1-1。你需要把每个 −1-1 独立替换为 [1,m][1,m] 内的任意整数。

求替换后可以得到多少个不同的神秘序列,答案对 109+710^9+7 取模。

只统计最终数组的不同取值方案;同一个数组即使有多种消除顺序,也只计一次。

输入格式

第一行两个整数 n,mn,m。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

输出一行一个整数,表示答案对 109+710^9+7 取模的结果。

数据范围

2≤n≤1062\le n\le10^6,1≤m≤1081\le m\le10^8。每个 aia_i 均满足 ai=−1a_i=-1 或 1≤ai≤m1\le a_i\le m。

样例 1

输入:

2 2
-1 -1

输出:

3

样例 2

输入:

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

输出:

9125