Następujące dwa kroki, wykonywane na tablicy $x$ składającej się z dodatnich liczb całkowitych, nazywamy operacją:

1. Wybierz dowolne dwa sąsiednie elementy w $x$, zmniejsz jeden z nich o $1$, a drugi ustaw na $0$.
2. Usuń wszystkie zera z $x$.

Tablicę $x$ nazywamy mistyczną wtedy i tylko wtedy, gdy można ją przekształcić w ciąg pusty po skończonej liczbie operacji (być może zerowej).

Dana jest tablica $a$ składająca się z $n$ liczb całkowitych oraz liczba całkowita $m$. Każdy element tablicy $a$ jest albo liczbą całkowitą od $1$ do $m$, albo wynosi $-1$. Twoim zadaniem jest zastąpienie każdego wystąpienia $-1$ w $a$ dowolną liczbą całkowitą od $1$ do $m$.

Wyznacz liczbę różnych mistycznych tablic $a$, które można otrzymać po zastąpieniu. Ponieważ odpowiedź może być bardzo duża, wypisz ją modulo $10^9 + 7$.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $n$ oraz $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^8$).

Drugi wiersz wejścia zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$ lub $a_i = -1$).

Wyjście

Wypisz jedną liczbę całkowitą, oznaczającą liczbę różnych mistycznych ciągów $a$, które można otrzymać, modulo $10^9 + 7$.

Przykłady

Przykładowe wejście 1

2 2
-1 -1

Przykładowe wyjście 1

3

Przykładowe wejście 2

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

Przykładowe wyjście 2

9125

Uwaga

W pierwszym teście tablica $a$ to $[-1, -1]$. Zastępując oba $-1$, jednym z możliwych wyników jest $[1, 2]$. W tym przypadku wybieramy dwie sąsiednie liczby: zmniejszamy pierwszą o $1$, a drugą ustawiamy na $0$, otrzymując $[0, 0]$. Po usunięciu wszystkich zer ciąg staje się pusty. Stąd $[1, 2]$ jest ciągiem mistycznym.

Podobnie, jeśli zastąpimy $-1$ przez $[1, 1]$ lub przez $[2, 1]$, oba ciągi również można zredukować do ciągu pustego. Zatem łączna liczba różnych ciągów mistycznych wynosi $3$.