Sirag

Fie un șir de caractere $S$ de lungime $N$ format din litere mici ale alfabetului englez. Pentru un $K$ oarecare ($K \geq 1$), alegem $K$ poziții $1 \leq i_1 < i_2 < i_3 < \dots < i_K < N$ în care să tăiem șirul, rezultând $K + 1$ șiruri, pe care le notăm cu $T_1, \ldots, T_{K + 1}$, astfel:

$$\begin{matrix} T_1 & = & S_1\, S_2\, \ldots\, S_{i_1} \\ T_2 & = & S_{i_1 + 1} \, S_{i_1 + 2}\, \ldots\, S_{i_2} \\ \vdots & \vdots & \vdots \\ T_{K + 1} & = & S_{i_k + 1} \, S_{i_k + 2}\, \ldots \, S_N \end{matrix}$$

Șirurile $T_1, \ldots, T_{K + 1}$ pot avea lungimi diferite.

Fie $C_i$ mulțimea caracterelor ce apar în $T_i$. Spunem că o tăiere este echilibrată dacă $|C_1| = |C_2| = \cdots = |C_{K + 1}|$ --- adică fiecare dintre șirurile $T_1, \ldots, T_{k + 1}$ conține la fel de multe caractere distincte.

Cerință

Considerăm toate subsecvențele șirului $S$ și pentru fiecare calculăm numărul de moduri de a o tăia echilibrat (în cel puțin două bucăți). Să se afișeze suma rezultatelor pentru toate subsecvențele modulo $1 \ 000 \ 000 \ 007$.

Date de intrare

Fișierul de intrare sirag.in conține pe prima linie un număr natural $N$, lungimea lui $S$. Pe a doua linie, se află șirul de caractere $S$.

Date de ieșire

Pe prima linie a fișierului de ieșire sirag.out se va scrie suma cerută modulo $1 \ 000 \ 000 \ 007$.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$

Exemplul 1

sirag.in

3
aaa

sirag.out

5

Explicație

Subsecvențele lui $S$ sunt:

• aaa - poate fi tăiat într-un singur mod pentru $K = 1$;
• aaa - poate fi tăiat într-un singur mod pentru $K = 1$;
• aaa - poate fi tăiat în $2$ moduri pentru $K = 1$ și un singur mod pentru $K = 2$.

Exemplul 2

sirag.in

6
aabbaa

sirag.out

43

Exemplul 3

sirag.in

20
aababbababbababhhsse

sirag.out

7027