Cerința

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 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.

Date de intrare

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

Date de ieșire

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

Restricții și precizări

• \(1 ≤ N ≤ 10^6\).

Subtask (20 puncte)

• \(N ≤ 15\).

Subtask (10 puncte)

• \(N ≤ 200\).

Subtask (20 puncte)

• \(N ≤ 2 000\).

Subtask (20 puncte)

• \(N ≤ 5 · 10^4\).

Subtask (30 puncte)

• Fară restricții suplimentare.

Exemplu:

Intrare

cab

Ieșire

8

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.

Exemplu:

Intrare

felicia

Ieșire

59