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