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