Tiedät, että taulukossa on $n$ lukua ja jokainen niistä on välillä $1 \dots m$. Lisäksi tiedät, että minkään kahden vierekkäisen luvun ero ei voi olla enemmän kuin $1$.

Sinulle annetaan taulukon kuvaus, jossa osa luvuista on tuntemattomia. Moniko taulukko voi täsmätä kuvaukseen?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: taulukon koko ja luvun suuruuden yläraja.

Seuraavalla rivillä on $n$ kokonaislukua $x_1,x_2,\dots,x_n$: taulukon sisältö. Luku $0$ tarkoittaa, että siinä kohtaa oleva luku on tuntematon.

Tuloste

Tulosta yksi kokonaisluku: mahdollisten taulukoiden määrä modulo $10^9+7$.

Rajat

• $1 \le n \le 10^5$
• $1 \le m \le 100$
• $0 \le x_i \le m$

Esimerkki

Syöte:

3 5
2 0 2

Tuloste:

3

Selitys: Taulukko voi olla $[2,1,2]$, $[2,2,2]$ tai $[2,3,2]$.