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

Poveste şi 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&#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

Fişierul de intrare $cntsubsirmax.in$ ...

Pe singura linie citită de la tastatură se va găsi şirul $s$.

h2. Date de ieşire

h2. Date de intrare

În fişierul de ieşire $cntsubsirmax.out$ ...

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

h2. Restricţii

* $... ≤ ... ≤ ...$

* $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$
* Pentru alte $20$ de puncte, $|s| ≤ 10.000$

h2. Exemplu

h3. Exemple

table(example). |_. cntsubsirmax.in |_. cntsubsirmax.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| cab
| 8
|
| felicia
| 59
|

h3. Explicaţie

...

Pentru primul exemplu, 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$.

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