De følgende to stegene på en tabell $x$ bestående av positive heltall kalles en operasjon:

1. Velg to vilkårlige naboelementer i $x$, reduser ett av dem med $1$, og sett det andre til $0$.
2. Fjern alle nuller fra $x$.

Vi kaller $x$ mystisk hvis og bare hvis den kan gjøres om til en tom følge etter et endelig antall operasjoner (muligens null).

Du får en tabell $a$ bestående av $n$ heltall, samt et heltall $m$. Hvert element i $a$ er enten et heltall fra $1$ til $m$ eller $-1$. Din oppgave er å erstatte hver forekomst av $-1$ i $a$ med et hvilket som helst heltall fra $1$ til $m$.

Bestem antallet ulike mystiske tabeller $a$ som kan oppnås etter erstatningen. Siden svaret kan være svært stort, skriv det ut modulo $10^9 + 7$.

Inndata

Den første linjen i inndataene inneholder to heltall $n$ og $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^8$).

Den andre linjen i inndataene inneholder $n$ heltall $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$ eller $a_i = -1$).

Utdata

Skriv ut et enkelt heltall som representerer antallet ulike mystiske følger $a$ som kan oppnås, modulo $10^9 + 7$.

Eksempler

Eksempelinndata 1

2 2
-1 -1

Eksempelutdata 1

3

Eksempelinndata 2

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

Eksempelutdata 2

9125

Forklaring

I den første testen er tabellen $a$ lik $[-1, -1]$. Ved å erstatte begge $-1$-ene er et mulig resultat $[1, 2]$. I dette tilfellet velger vi de to nabotallene: reduserer det første med $1$ og setter det andre til $0$, slik at vi får $[0, 0]$. Etter å ha fjernet alle nuller blir følgen tom. Derfor er $[1, 2]$ en mystisk følge.

Tilsvarende, hvis vi erstatter $-1$-ene med $[1, 1]$ eller med $[2, 1]$, kan begge følgene også reduseres til en tom følge. Derfor er det totale antallet ulike mystiske følger $3$.