對一個由正整數組成嘅陣列 $x$ 進行以下兩個步驟，稱為一次操作：

1. 喺 $x$ 入面揀任意兩個相鄰嘅元素，將其中一個減 $1$，並將另一個設為 $0$。
2. 由 $x$ 入面刪走所有嘅零。

我哋稱 $x$ 係神秘嘅（mystic），當且僅當佢可以喺有限次操作（可以係零次）之後變成一個空序列。

俾你一個由 $n$ 個整數組成嘅陣列 $a$，以及一個整數 $m$。$a$ 入面嘅每個元素一係係 $1$ 到 $m$ 之間嘅整數，一係係 $-1$。你嘅任務係將 $a$ 入面所有出現嘅 $-1$ 替換成 $1$ 到 $m$ 之間嘅任意整數。

求替換之後可以得到嘅唔同神秘陣列 $a$ 嘅數量。由於答案可能好大，請將答案對 $10^9 + 7$ 取模後輸出。

輸入格式

輸入嘅第一行包含兩個整數 $n$ 同 $m$（$2 \le n \le 10^6$，$1 \le m \le 10^8$）。

輸入嘅第二行包含 $n$ 個整數 $a_1, a_2, \dots, a_n$（$1 \le a_i \le m$ 或者 $a_i = -1$）。

輸出格式

輸出一個整數，代表可以得到嘅唔同神秘序列 $a$ 嘅數量，對 $10^9 + 7$ 取模之後嘅結果。

範例

範例輸入 1

2 2
-1 -1

範例輸出 1

3

範例輸入 2

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

範例輸出 2

9125

說明

喺第一個測試入面，陣列 $a$ 係 $[-1, -1]$。透過替換兩個 $-1$，一種可能嘅結果係 $[1, 2]$。喺呢種情況下，我哋揀兩個相鄰嘅數：將第一個數減 $1$，並將第二個數設為 $0$，得到 $[0, 0]$。刪走所有零之後，序列變成空。因此，$[1, 2]$ 係一個神秘序列。

同樣道理，如果我哋將啲 $-1$ 替換成 $[1, 1]$ 或者 $[2, 1]$，呢兩個序列亦都可以化為空。因此，唔同嘅神秘序列總數係 $3$。