Dan je broj \(n\) i niz od \(n\) prirodnih brojeva. Na koliko načina možete maknut neke od brojeva tako da niz postane strogo rastući?

Svoje rješenje ispišite modulo \(10^9+7\).

Prazan niz se smatra rastućim.

Ulazni podatci

U prvom retku nalazi se prirodan broj \(n\) (\(1 \leq n \leq 10^5\)), duljina niza. U sljedećem retku nalazi se \(n\) brojeva, svaki broj \(x_i\) je \(1 \leq x_i \leq 10^5\).

Izlazni podatci

Ispišite jedan broj, broj rastućih podnizova modulo \(10^9 + 7\).

Podzadatci

Ulaz primjera 1

3
2 1 3

Izlaz primjera 1

6

Pojašnjenje primjera 1

Rastući podnizovi su

1. 
2. 2
3. 1
4. 3
5. 2 3
6. 1 3

Ulaz primjera 2

3
1 2 3

Izlaz primjera 2

8