Definim distanța dintre două șiruri de caractere de aceeași lungime ca fiind numărul minim de caractere ce trebuie modificate (înlocuite fiecare cu câte un alt caracter) în primul șir pentru a obține al doilea șir. Vom nota distanța dintre șirurile a și b cu dist(a, b). De exemplu, dist("abc", "aaa") = 2 (înlocuim caracterul b cu a, respectiv caracterul c cu a), iar dist("ABC", "abc") = 3 (literele mici se consideră diferite de cele mari).

Definim o subsecvență a unui șir s de caractere ca fiind un șir format din caractere de pe poziții consecutive din s. Considerăm două subsecvențe ca fiind distincte dacă încep sau se termină la poziții diferite. Vom nota cu s(i, j) subsecvența formată din caracterele indexate de la i la j ale șirului s. Șirurile se indexează de la 0. Exemplu: pentru șirul s ="abc" subsecvențele sunt s(0, 0) = "a", s(1, 1) = "b", s(2, 2) = "c", s(0, 1) = "ab", s(1, 2) = "bc", s(0, 2) = "abc", iar pentru șirul s = "aa" acestea sunt s(0, 0) = "a", s(1, 1) = "a", s(0, 1) = "aa".

Cerința

Se dă un șir de caractere s, care poate conține doar litere mici și mari ale alfabetului englez (de la a la z și de la A la Z). Pentru toate perechile neordonate de subsecvențe distincte ale șirului s care au lungimi egale, vrem să calculăm distanța dintre ele și să afișăm suma acestora modulo 1.000.000.007. Formal, se cere suma valorilor dist(s(a, b), s(c, d)), pentru toți indicii a, b, c, d cu 0 ≤ a, b, c, d < |s|, a < c, a ≤ b, c ≤ d, b - a = d - c, modulo 1.000.000.007. |s| reprezintă lungimea șirului s, care este indexat de la 0.

Date de intrare

Fișierul de intrare sdistante.in conține pe prima linie șirul dat s.

Date de ieșire

Se va afișa pe singurul rând al fișierului sdistante.out un număr întreg reprezentând suma distanțelor, modulo 1.000.000.007.

Restricții și precizări

• 1 ≤ |s| ≤ 4.000.000, unde |s| este lungimea șirului s
• Pentru 11 puncte, |s| ≤ 20 și s conține doar litere mici
• Pentru alte 5 puncte, |s| ≤ 50 și s conține doar caracterele a și b
• Pentru alte 15 puncte, |s| ≤ 350 și s conține doar litere mici
• Pentru alte 6 puncte, |s| ≤ 1000 și s conține doar caracterele a și b
• Pentru alte 30 puncte, |s| ≤ 5000 și s conține doar litere mici
• Pentru alte 5 puncte, |s| ≤ 100.000 și s conține doar caracterele a și b
• Pentru alte 4 puncte, |s| ≤ 100.000 și s conține doar litere mici
• Pentru alte 6 puncte, |s| ≤ 1.000.000 și s conține doar caracterele a și b
• Pentru alte 6 puncte, fără restricții

Exemplul 1:

sdistante.in

abc

sdistante.out

5

Explicație

• dist(s(0, 0), s(1, 1)) = dist("a", "b") = 1
• dist(s(0, 0), s(2, 2)) = dist("a", "c") = 1
• dist(s(1, 1), s(2, 2)) = dist("b", "c") = 1
• dist(s(0, 1), s(1, 2)) = dist("ab", "bc") = 2

Exemplul 2:

sdistante.in

aab

sdistante.out

3

Explicație

• dist(s(0, 0), s(1, 1)) = dist("a"; "a") = 0
• dist(s(0, 0), s(2, 2)) = dist("a"; "b") = 1
• dist(s(1, 1), s(2, 2)) = dist("a"; "b") = 1
• dist(s(0, 1), s(1, 2)) = dist("aa"; "ab") = 1

Exemplul 3:

sdistante.in

ABa

sdistante.out

5

Explicație

• dist(s(0, 0), s(1, 1)) = dist("A"; "B") = 1
  • dist(s(0, 0), s(2, 2)) = dist("A"; "a") = 1
  • dist(s(1, 1), s(2, 2)) = dist("B"; "a") = 1
  • dist(s(0, 1), s(1, 2)) = dist("AB"; "Ba") = 2

Exemplul 4:

sdistante.in

aaaaabbbaaaa

sdistante.out

480

Exemplul 5:

sdistante.in

abcdefghizabcdefghiz

sdistante.out

7095