正の整数からなる配列 $x$ に対する次の 2 つのステップを 1 回の操作と呼びます：

1. $x$ 内の隣接する 2 つの要素を任意に選び、一方を $1$ 減らし、もう一方を $0$ にする。
2. $x$ からすべてのゼロを取り除く。

有限回（0 回でもよい）の操作の後に空の列に変換できるとき、かつそのときに限り、$x$ を神秘的（mystic）と呼びます。

$n$ 個の整数からなる配列 $a$ と、整数 $m$ が与えられます。$a$ の各要素は $1$ 以上 $m$ 以下の整数、または $-1$ です。あなたの仕事は、$a$ に含まれるすべての $-1$ をそれぞれ $1$ 以上 $m$ 以下の任意の整数に置き換えることです。

置き換えによって得られる相異なる神秘的な配列 $a$ の個数を求めてください。答えは非常に大きくなる可能性があるため、$10^9 + 7$ で割った余りを出力してください。

入力

入力の 1 行目には、2 つの整数 $n$ と $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^8$) が与えられます。

入力の 2 行目には、$n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$ または $a_i = -1$) が与えられます。

出力

得られる相異なる神秘的な列 $a$ の個数を $10^9 + 7$ で割った余りを表す 1 つの整数を出力してください。

入出力例

入力例 1

2 2
-1 -1

出力例 1

3

入力例 2

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

出力例 2

9125

ノート

1 番目のテストでは、配列 $a$ は $[-1, -1]$ です。両方の $-1$ を置き換えた結果としてあり得るものの 1 つは $[1, 2]$ です。この場合、隣接する 2 つの数を選び、最初の数を $1$ 減らして 2 番目の数を $0$ にすると、$[0, 0]$ が得られます。すべてのゼロを取り除くと、列は空になります。したがって、$[1, 2]$ は神秘的な列です。

同様に、$-1$ を置き換えて $[1, 1]$ や $[2, 1]$ にした場合も、どちらの列も空にすることができます。したがって、相異なる神秘的な列の総数は $3$ です。