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

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

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

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=$ ``\texttt{aa}" acestea sunt $s(0,0)=$``\texttt{a}", $s(1,1)=$``\texttt{a}", $s(0,1)=$ ``\texttt{aa}".

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

Se dă un şir de caractere $s$, care poate conţine doar litere mici şi mari ale alfabetului englez (de la `\texttt{a}' la `\texttt{z}' şi de la `\texttt{A}' la `\texttt{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 $10^9 + 7$. Formal, se cere suma valorilor $\textit{dist}( s(a, b), s(c, d) )$, pentru toţi indicii $a, b, c, d$ cu $0 \le a, b, c, d < |s|$, $a < c$, $a \le b$, $c \le d$, $b-a = d-c$, \textbf{modulo $\mathbf{10^9 + 7}$}. $|s|$ reprezintă lungimea şirului $s$, care este indexat de la $0$.

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 $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 &le; a, b, c, d < |s|$, $a < c$, $a &le; b$, $c &le; d$, $b-a = d-c$, *modulo* $10^9^ + 7$. $|s|$ reprezintă lungimea şirului $s$, care este indexat de la $0$.

h2. Date de intrare

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

Pe singura linie a fişierului $sdistante.in$ este şirul dat, $s$.

h2. Date de ieşire

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

Se va afişa pe singurul rând al fişierului $sdistante.out$ un număr întreg reprezentând suma distanţelor, *modulo* $10^9^ + 7$.

h2. Restricţii

h2. Restricţii şi precizări

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

* $|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| ≤ 1.000$ şi $s$ conţine doar caracterele $a$ şi $b$.
* Pentru alte 30 de puncte $|s| ≤ 5.000$ ş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$.
* *Atenţie!* Este posibil ca punctajul să difere faţă de cel luat în concurs.

h2. Exemplu

h2. Exemple

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

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

| abc | 5 |
| aab | 3 |
| ABa | 5 |
| aaaaabbbaaaa | 480 |
| abcdefghizabcdefghiz | 7095 |
 
h3. Explicaţii
 
Pentru primul exemplu,
 
* $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$
 
Pentru al doilea exemplu,
 
* $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$
 
Pentru al treilea exemplu,
 
* $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$

h3. Explicaţie
 
...

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