Die folgenden zwei Schritte auf einem Array $x$, das aus positiven ganzen Zahlen besteht, werden als eine Operation bezeichnet:

1. Wähle zwei beliebige benachbarte Elemente in $x$, verringere eines davon um $1$ und setze das andere auf $0$.
2. Entferne alle Nullen aus $x$.

Wir nennen $x$ mystisch, wenn und nur wenn es nach einer endlichen Anzahl von Operationen (möglicherweise null) in eine leere Folge umgewandelt werden kann.

Gegeben ist ein Array $a$, das aus $n$ ganzen Zahlen besteht, sowie eine ganze Zahl $m$. Jedes Element von $a$ ist entweder eine ganze Zahl von $1$ bis $m$ oder $-1$. Deine Aufgabe ist es, jedes Vorkommen von $-1$ in $a$ durch eine beliebige ganze Zahl von $1$ bis $m$ zu ersetzen.

Bestimme die Anzahl der verschiedenen mystischen Arrays $a$, die nach dem Ersetzen erhalten werden können. Da die Antwort sehr groß sein kann, gib sie modulo $10^9 + 7$ aus.

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen $n$ und $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^8$).

Die zweite Zeile der Eingabe enthält $n$ ganze Zahlen $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$ oder $a_i = -1$).

Ausgabe

Gib eine einzelne ganze Zahl aus, die die Anzahl der verschiedenen mystischen Folgen $a$ darstellt, die erhalten werden können, modulo $10^9 + 7$.

Beispiele

Beispieleingabe 1

2 2
-1 -1

Beispielausgabe 1

3

Beispieleingabe 2

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

Beispielausgabe 2

9125

Hinweis

Im ersten Beispiel ist das Array $a$ gleich $[-1, -1]$. Durch Ersetzen beider $-1$ ist ein mögliches Ergebnis $[1, 2]$. In diesem Fall wählen wir die beiden benachbarten Zahlen: Wir verringern die erste um $1$ und setzen die zweite auf $0$, wodurch wir $[0, 0]$ erhalten. Nach dem Entfernen aller Nullen wird die Folge leer. Folglich ist $[1, 2]$ eine mystische Folge.

Wenn wir die $-1$ analog durch $[1, 1]$ oder durch $[2, 1]$ ersetzen, lassen sich beide Folgen ebenfalls auf eine leere Folge reduzieren. Daher beträgt die Gesamtzahl der verschiedenen mystischen Folgen $3$.