Trumperika

când vaporul se scufundă, șobolanii se scufundă și ei.

În regatul $\text{Tramperika}$ , prea iubitul rege, $\text{Murp Dorald}$, se gândește serios cum să-și taxeze cât mai bine discipolii. Regatul este compus din $N$ districte, fiecare fiind codificat cu un caracter ($a,b, \dots, z$). Toate districtele codificate cu același caracter formează o alianța, iar cu cât alianța este alcătuită dintr-un număr mai mare de districte, cu atât împăratul nostru suveranist își face mai multe griji. Însă consilierul regal, $\text{Eleonor}$, concepe un plan eficient de a calma apele, și cum orice alt om înțelept are face, definește taxa unui interval $[l,r]$ ca fiind $\displaystyle \sum_{i = a}^{z} ord(i)^{fr(i)}$, unde $fr(i)$ reprezintă câte districte formează o alianța cu codul $i$, iar $ord(i)$ este egal cu poziția în aflabet a literei $i$.

De exemplu, considerăm șirul $\color{#87CEEB}a \color{#FFC300}b \color{#87CEEB}a \color{#00ff6f}c \color{#FFC300}b \color{#FFC300}b \color{#00ff6f}c$, de unde deducem că taxa va fi egală cu $1^{2} + 2^{3} + 3^{2} + 4^{0} + \dots + 26^{0} = 41$.

Cerință

Auzind de ideea măreață a lui $\text{Eleonor}$, $\text{Dorald}$ rămâne uimit, și se întreabă care ar fi suma taxelor tuturor intervalelor. În ciuda înclinațiilor voastre morale, rolul vostru este să calculați suma cerută de rege și să o afișați pe ecran $\text{modulo} \ \ 10^9 + 7$.

Date de intrare

Pe prima linie se află $T$, numărul de subteste. Pe prima linie din fiecare subtest se află $N$, numărul de districte, iar pe următoarea linie se află un șir $S$ de caractere de lungime $N$.

Date de ieșire

Pe fiecare dintre cele $T$ linii se va afișa suma cerută pentru subtestul aferent.

Restricții și precizări

• $1 \leq T \leq 100$.
• Fie $Sm$ suma numerelor de districte din cele $T$ subteste.
• $1 \leq Sm \leq 2 \cdot 10^5$.

  #	Scor	Restricții
  1	12	$1 \leq N \leq 10, Sm \leq 1 \ \ 000$
  2	20	$1 \leq Sm \leq 10^4$
  3	10	$S_i = a$
  4	15	$T \leq 2, S_i = a \ \ \text{sau} \ \ S_i = \text{b și numărul de caractere egale cu b} \leq 10^4$
  5	43	$\text{Fără restricții}$

Exemplul 1

trumperika.in

5
10
fwcmxivdzu
1
b
10
cqwyywzywh
2
og
5
naovo

trumperika.out

4500
27
281184
118
1407