CntSubsirMax

Cerință

Felicia este interesată de subșirul maxim lexicografic al unui șir de caractere. Rețineți că un șir $a$ este considerat mai mic în ordine lexicografică decât un șir $b$ dacă $a$ este prefix al lui $b$, sau dacă există o poziție $i$ pentru care avem $a[1] = b[1]$, $...$, $a[i-1] = b[i-1]$, și $a[i] \lt b[i]$. Astfel, subșirul maxim lexicografic al unui șir de caractere este cel mai mare subșir, în ordinea lexicografică, al unui șir de caractere (de exemplu zzxx pentru azbxazbxaax). Pentru un șir $s$ de caractere vom nota cu $m(s)$ subșirul maxim lexicografic al lui $s$, și cu $v(s) = |m(s)|$ lungimea acestui subșir.

Felicia vă dă un șir $s$ format din caractere mici ale alfabetului englez. Considerați toate subsecvențele continue $s^{\prime}$ ale lui $s$. Felicia vrea să calculați suma valorilor $v(s^{\prime})$ pentru toate subsecvențele posibile $s^{\prime}$ amintite anterior.

Date de intrare

Pe singura linie citită se va găsi șirul $s$.

Date de ieșire

Să se afișeze suma cerută, modulo $10^9 + 7$.

Restricții

• $1 \leq N \leq 10^6$

Subtask 1 (20 puncte)

• $N \leq 15$

Subtask 2 (10 puncte)

• $N \leq 200$

Subtask 3 (20 puncte)

• $N \leq 2 \ 000$

Subtask 4 (20 puncte)

• $N \leq 5 \cdot 10^4$

Subtask 5 (30 puncte)

• Fără restricții suplimentare.

Exemplul 1

stdin

cab

stdout

8

Explicație

Observăm că $m(c) = c$, $m(a) = a$, $m(b) = b$, $m(ca) = ca$, $m(ab) = b$, $m(cab) = cb$. Astfel, răspunsul este $1+1+1+2+1+2=8$

Exemplul 2

stdin

felicia

stdout

59