== include(page="template/taskheader" task_id="cntsubsirmax") ==

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] < 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 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&#91;1] = b&#91;1]$, ..., $a[i - 1] = b[i - 1]$, şi $a[i] < 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'$ ale lui $s$. Felicia vrea să calculaţi suma valorilor $v(s')$ pentru toate subsecvenţele posibile $s'$ amintite anterior.

h2. Date de intrare

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

Să se afişeze suma cerută, modulo $1.000.000.007$.

h2. Restricţii

* $1 ≤ |s| ≤ 10^6$

* $1 ≤ |s| ≤ 1.000.000$

* Pentru $20$ de puncte, $|s| ≤ 15$
* Pentru alte $10$ de puncte, $|s| ≤ 200$
* Pentru alte $20$ de puncte, $|s| ≤ 2.000$