CSES - Lukujonot
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Sinulla on taulukko, jossa on $n$ 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 $n$: taulukon koko.

Seuraavalla rivillä on $n$ kokonaislukua $x_1,x_2,\ldots,x_n$: taulukon sisältö.

Tuloste

Tulosta yksi kokonaisluku: lukujonojen määrä modulo $10^9+7$.

Rajat
  • $1 \le n \le 5 \cdot 10^5$
  • $1 \le x_i \le 10^9$
Esimerkki

Syöte:
3
1 2 1


Tuloste:
6

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