CSES - Uusi aita
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Juuri kun Uolevi oli saanut aitansa valmiiksi, seudulle saapui pyörremyrsky, joka tuhosi suurimman osan aidasta. Nyt Uolevi joutuu rakentamaan jälleen uuden aidan.

Tällä kertaa Uolevi haluaa rakentaa aidan, jossa jokaisen kahden vierekkäisen laudan korkeuden ero on tarkalleen 1.

Kun annettuna on aidan nykyisten lautojen korkeudet (myrsky ei tuhonnut kaikkia lautoja), tehtäväsi on laskea, montako erilaista aitaa Uolevi voi rakentaa.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: aidan lautojen määrä.

Seuraavalla rivillä on n kokonaislukua a_1,a_2,\ldots,a_n: kunkin laudan korkeus. Jos korkeus on 0, kyseinen lauta on tuhoutunut ja Uolevi korvaa sen uudella laudalla. Jos korkeus on positiivinen, lauta on valmiina eikä Uolevi muuta sitä.

Ainakin yksi aidan laudoista säästyi myrskyltä.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: montako erilaista aitaa Uolevi voi rakentaa. Jokaisen laudan korkeuden tulee olla vähintään 1 (voi olla myös yli 100). Vastaus voi olla suuri, joten tulosta se modulo 10^9+7.

Vastaus voi olla myös 0, jos Uolevi ei voi rakentaa mitenkään haluamaansa aitaa.

Rajat

  • 1 \le n \le 100
  • 0 \le a_k \le 100

Esimerkki

Syöte:

6
3 0 0 0 5 0

Tuloste:

8

Selitys: Mahdolliset aidat ovat seuraavat:

  • 3, 2, 3, 4, 5, 4
  • 3, 2, 3, 4, 5, 6
  • 3, 4, 3, 4, 5, 4
  • 3, 4, 3, 4, 5, 6
  • 3, 4, 5, 4, 5, 4
  • 3, 4, 5, 4, 5, 6
  • 3, 4, 5, 6, 5, 4
  • 3, 4, 5, 6, 5, 6