CSES - Lukujonot
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Sinulla on taulukko, jossa on nn kokonaislukua. Kuljet taulukon läpi vasemmalta oikealle ja poimit matkalla haluamasi luvut.

Montako erilaista epätyhjää lukujonoa voit muodostaa tällä tavalla?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku nn: taulukon koko.

Seuraavalla rivillä on nn kokonaislukua x1,x2,,xnx_1,x_2,\ldots,x_n: taulukon sisältö.

Tuloste

Tulosta yksi kokonaisluku: lukujonojen määrä modulo 109+710^9+7.

Rajat

  • 1n51051 \le n \le 5 \cdot 10^5
  • 1xi1091 \le x_i \le 10^9

Esimerkki

Syöte:

3
1 2 1

Tuloste:

6

Selitys: Lukujonot ovat (1)(1), (2)(2), (1,1)(1,1), (1,2)(1,2), (2,1)(2,1) ja (1,2,1)(1,2,1).