4. Opačné čítanie

S jeseňou okrem chladného počasia a padania listov prichádza aj nový školský rok a Adam musel opäť nastúpiť do školy. Keďže sa do školy vrátiť nechcel, vymýšlal všelijaké výhovorky, aby mohol zostať doma (napr. strčil teplomer do teplého čaju; presviedčal rodičov, že je stále august; schoval sa pod posteľ; …). Tie sa mu však neprepiekli a do školy išiel aj tak.

Ako tam sedel, už na druhej vyučovacej hodine, uvedomil si, že to napokon nie je až také zlé. Čo ale čert nechcel, cez veľkú prestávku si spolužiaci začali robiť srandu z jeho štíhlej stavby tela. Na lavici mu pristál papierik so slovami Madam Adam. Adama to trošku rozhodilo a spýtal sa učiteľky, či by sa dalo ísť domov. Učiteľka mysliac, že sa pýtal na záchod, ho s úsmevom na perách pustila.

Po príchode domov si ešte raz otvoril papierik s odkazom. Ako sa naň pozeral, uvedomil si zaujímavú vec – madamadam sa číta rovnako spredu aj zo zadu. Takáto vlastnosť sa Adamovi veľmi zapáčila a vymyslel si takých slov viac. Ba dokonca, vymyslel ku takýmto slovám zaujímavú úlohu.

Úloha

Adam vymyslel n stringov s k znakmi, ktoré sa čítajú rovnako spredu aj zo zadu. String obsahuje znaky a-z, A-Z a 0-9. Okrem toho, v každom stringu je každý unikátny znak maximálne dvakrát. Vašou úlohou je zistiť, koľkými rôznymi spôsobmi sa dajú vymazať znaky zo stringu, aby sa nečítal rovnako spredu aj zo zadu.

Formát vstupu

Na prvom riadku vstupu je číslo n, ktoré reprezentuje počet otázok. Potom nasleduje n riadkov a na každom z nich je string dĺžky k.

Formát výstupu

Na každý riadok vypíšte číslo, koľkými rôznymi spôsobmi vieme vymazať znaky v stringu, aby sa nedal prečítať rovnako spredu aj zo zadu. Keďže odpoveď môže byť veľmi veľká, vypisujte ju modulo \(10^9 + 7\).

Obmedzenia

Sú \(4\) sady vstupov po \(2\) body. Platia v nich nasledovné obmedzenia:

Príklad

Input:

1
AbbA

Output:

6

Po vymazaní znakov zo stringu AbbA je týchto 6 možných stringov, ktoré sa nečítajú rovnako spredu aj zo zadu: Abb, Ab, Ab, bbA, bA, bA. Na prvý pohľad sa zdá, že stringy Ab a Ab sú rovnaké, lenže jeden string obsahuje znak b na prvom indexe a druhý obsahuje znak b na druhom indexe, čiže sú rôzne. Tak isto aj bA a bA.

Input:

2
DaL00LaD
bysAsyb

Output:

210
98

Zo stringu DaL00LaD sa dajú vymazať znaky 210 spôsobmi a zo stringu bysAsyb sa dajú vymazať znaky 98 spôsobmi, aby sa nečítali rovnako spredu aj zo zadu.