CSES - Alijonot
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Sinulla on taulukko, jossa on $n$ kokonaislukua, ja haluat laskea, montako nousevaa alijonoa taulukossa on.

Nouseva alijono sisältää joukon taulukon alkioita vasemmalta oikealle niin, että jokainen alkio on suurempi kuin edellinen alkio.

Huomaa, että jos kaksi alijonoa sisältävät samat luvut mutta eri kohdista otettuina, ne lasketaan erikseen.

Syöte

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

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

Tuloste

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

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

Syöte:
3
2 1 3


Tuloste:
5

Selitys: Alijonot ovat $[2]$, $[1]$, $[3]$, $[2,3]$ ja $[1,3]$.