CSES - 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
  • $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]$.