Följande två steg på ett fält $x$ bestående av positiva heltal kallas en operation:

1. Välj två godtyckliga intilliggande element i $x$, minska ett av dem med $1$ och sätt det andra till $0$.
2. Ta bort alla nollor från $x$.

Vi kallar $x$ mystiskt om och endast om det kan omvandlas till en tom följd efter ett ändligt antal operationer (möjligen noll).

Du får ett fält $a$ bestående av $n$ heltal, samt ett heltal $m$. Varje element i $a$ är antingen ett heltal från $1$ till $m$ eller $-1$. Din uppgift är att ersätta varje förekomst av $-1$ i $a$ med valfritt heltal från $1$ till $m$.

Bestäm antalet distinkta mystiska fält $a$ som kan erhållas efter ersättningen. Eftersom svaret kan vara mycket stort, skriv ut det modulo $10^9 + 7$.

Indata

Den första raden i indatan innehåller två heltal $n$ och $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^8$).

Den andra raden i indatan innehåller $n$ heltal $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$ eller $a_i = -1$).

Utdata

Skriv ut ett enda heltal som representerar antalet distinkta mystiska följder $a$ som kan erhållas, modulo $10^9 + 7$.

Exempel

Exempelindata 1

2 2
-1 -1

Exempelutdata 1

3

Exempelindata 2

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

Exempelutdata 2

9125

Förklaring

I det första testet är fältet $a$ lika med $[-1, -1]$. Genom att ersätta båda $-1$:orna är ett möjligt resultat $[1, 2]$. I detta fall väljer vi de två intilliggande talen: minskar det första med $1$ och sätter det andra till $0$, vilket ger $[0, 0]$. Efter att alla nollor tagits bort blir följden tom. Alltså är $[1, 2]$ en mystisk följd.

På liknande sätt, om vi ersätter $-1$:orna med $[1, 1]$ eller med $[2, 1]$, kan båda följderna också reduceras till en tom följd. Därför är det totala antalet distinkta mystiska följder $3$.