SOLINFO.ro Runda 3 | NSC

Gigel a învățat la școală despre subșirul strict crescător de lungime maximă. Cum acesta este foarte curios de fel, s-a întrebat câte astfel de subșiruri strict crescătoare de lungime maximă există într-un șir $S$.

Cerință

Dându-se șirul $S$, format din numere naturale nenule, să se determine numărul de subșiruri strict crescătoare de lungime maximă din acesta.

Date de intrare

Programul citește de la tastatură numărul natural $N$, aflat pe prima linie. Pe a doua linie, se vor regăsi $N$ numere naturale nenule separate printr-un spațiu, reprezentând elementele șirului $S$.

Date de ieșire

Programul va afișa numărul de subșiruri strict crescătoare de lungime maximă din șirul $S$. Deoarece acest număr poate fi foarte mare, acesta trebuie afișat modulo $1\ 000\ 000\ 007$.

Restricții și precizări

• $1 \leq N \leq 100\ 000$
• Fiecare element din șir este $\leq 2\ 000\ 000\ 000$.
• Pentru 20 de puncte, $1 \leq N \leq 100$.
• Pentru încă 20 de puncte, $1 \leq N \leq 5\ 000$.
• Un subșir este format din unul sau mai multe elemente în ordine din șirul dat, nu neapărat pe poziții consecutive.
• Distincția dintre două subșiruri se face prin pozițiile elementelor, nu prin valorile acestora.
• Elementele șirului sunt indexate de la 1.

Exemplu

stdin

10
2 3 4 1 2 3 5 9 1 9

stdout

4

Explicație

Există 4 subșiruri strict crescătoare de lungime maximă. Acestea sunt $\{2, 3, 4, 5, 9\}$, $\{1, 2, 3, 5, 9\}$, $\{2, 3, 4, 5, 9\}$ și $\{1, 2, 3, 5, 9\}$. Primele două subșiruri îl au pe $9$ de pe poziția $8$, iar ultimele două subșiruri îl au pe $9$ de pe poziția $10$.
$4\ mod\ 1\ 000\ 000\ 007 = 4$.