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=$ aa acestea sunt $s(0,0) = a, s(1,1) = a, s(0,1) = aa$.

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 ş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 de 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 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. Exemple