SDistanțe

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ță

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 $\text{mod }10^9 + 7$.

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$, $\text{mod }10^9 + 7$. $|s|$ reprezintă lungimea șirului $s$, care este indexat de la $0$.

Date de intrare

Pe singura linie a fișierului sdistante.in este ș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, $\text{mod }10^9 + 7$.

Restricții și precizări

• $|s| ≤ 4 \ 000 \ 000$, unde $|s|$ este lungimea șirului $s$.
• Pentru $11$ puncte, $|s| ≤ 20$, $s$ conține doar litere mici.
• Pentru alte 5 puncte, $|s| ≤ 50$, $s$ conține doar caracterele a și b.
• Pentru alte 15 puncte, $|s| ≤ 350$, $s$ conține doar litere mici.
• Pentru alte 6 puncte, $|s| ≤ 1 \ 000$, $s$ conține doar caracterele a și b.
• Pentru alte 30 puncte, $|s| ≤ 5 \ 000$, $s$ conține doar litere mici.
• Pentru alte 5 puncte, $|s| ≤ 100 \ 000$, $s$ conține doar caracterele a și b.
• Pentru alte 4 puncte, $|s| ≤ 100 \ 000$, $s$ conține doar litere mici.
• Pentru alte 6 puncte, $|s| ≤ 1 \ 000 \ 000$, $s$ conține doar caracterele a și b.
• Pentru alte 18 puncte, fără restricții suplimentare.

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