CntSubsirMax

Time limit: 0.1s
Memory limit: 64MB
Input:
Output:

Cerință

Felicia este interesată de subșirul maxim lexicografic al unui șir de caractere. Rețineți că un șir aa este considerat mai mic în ordine lexicografică decât un șir bb dacă aa este prefix al lui bb, sau dacă există o poziție ii pentru care avem a[1]=b[1]a[1] = b[1], ......, a[i1]=b[i1]a[i-1] = b[i-1], și a[i]<b[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 ss de caractere vom nota cu m(s)m(s) subșirul maxim lexicografic al lui ss, și cu v(s)=m(s)v(s) = |m(s)| lungimea acestui subșir.

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

Date de intrare

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

Date de ieșire

Să se afișeze suma cerută, modulo 109+710^9 + 7.

Restricții

  • 1N1061 \leq N \leq 10^6

Subtask 1 (20 puncte)

  • N15N \leq 15

Subtask 2 (10 puncte)

  • N200N \leq 200

Subtask 3 (20 puncte)

  • N2 000N \leq 2 \ 000

Subtask 4 (20 puncte)

  • N5104N \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)=cm(c) = c, m(a)=am(a) = a, m(b)=bm(b) = b, m(ca)=cam(ca) = ca, m(ab)=bm(ab) = b, m(cab)=cbm(cab) = cb. Astfel, răspunsul este 1+1+1+2+1+2=81+1+1+2+1+2=8

Exemplul 2

stdin

felicia

stdout

59

Problem info

ID: 15

Editor: AlexVasiluta

Author:

Source: InfoPro, Etapa II, Grupa A

Tags:

InfoPro Etapa II, Grupa A

Log in or sign up to be able to send submissions!