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].