Problem 15: 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

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