Seuraavia kahta vaihetta positiivisista kokonaisluvuista koostuvalle taulukolle $x$ kutsutaan operaatioksi:

1. Valitse mitkä tahansa kaksi vierekkäistä alkiota taulukosta $x$, vähennä toista niistä luvulla $1$ ja aseta toinen arvoon $0$.
2. Poista kaikki nollat taulukosta $x$.

Kutsumme taulukkoa $x$ mystiseksi täsmälleen silloin, kun se voidaan muuttaa tyhjäksi jonoksi äärellisen monta kertaa (mahdollisesti nolla kertaa) suoritetun operaation jälkeen.

Annetaan $n$ kokonaisluvusta koostuva taulukko $a$ sekä kokonaisluku $m$. Jokainen taulukon $a$ alkio on joko kokonaisluku väliltä $1$:stä $m$:ään tai $-1$. Tehtäväsi on korvata jokainen luvun $-1$ esiintymä taulukossa $a$ millä tahansa kokonaisluvulla väliltä $1$:stä $m$:ään.

Määritä korvaamisen jälkeen saatavien erilaisten mystisten taulukoiden $a$ lukumäärä. Koska vastaus voi olla hyvin suuri, tulosta se modulo $10^9 + 7$.

Syöte

Syötteen ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^8$).

Syötteen toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$ tai $a_i = -1$).

Tuloste

Tulosta yksi kokonaisluku, joka kuvaa saatavien erilaisten mystisten jonojen $a$ lukumäärää modulo $10^9 + 7$.

Esimerkit

Esimerkkisyöte 1

2 2
-1 -1

Esimerkkituloste 1

3

Esimerkkisyöte 2

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

Esimerkkituloste 2

9125

Huomautus

Ensimmäisessä testissä taulukko $a$ on $[-1, -1]$. Korvaamalla molemmat $-1$-luvut yksi mahdollinen tulos on $[1, 2]$. Tässä tapauksessa valitsemme kaksi vierekkäistä lukua: vähennämme ensimmäistä luvulla $1$ ja asetamme toisen arvoon $0$, jolloin saamme $[0, 0]$. Kaikkien nollien poistamisen jälkeen jonosta tulee tyhjä. Siispä $[1, 2]$ on mystinen jono.

Vastaavasti, jos korvaamme $-1$-luvut jonolla $[1, 1]$ tai jonolla $[2, 1]$, molemmat jonot voidaan myös supistaa tyhjiksi. Näin ollen erilaisten mystisten jonojen kokonaismäärä on $3$.