Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Taulukko


Task | Statistics


CSES - TaulukkoCSES - Taulukko

Time limit:1.00 s Memory limit:512 MB

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
Esimerkki

Syöte:
3 5
2 0 2


Tuloste:
3

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