Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Alijonot


Task | Statistics


CSES - AlijonotCSES - 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
Esimerkki

Syöte:
3
2 1 3


Tuloste:
5

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