cod

Doi fraţi, Ionică şi Florin, merg cu părinţii în Antalya la mare. Hotelul la care se cazează conţine un seif. Ionică, fratele mai mare, este copil liniştit, în schimb Florin este mereu pus pe şotii. Cum a ajuns în Antalya, Florin şi-a cumpărat o jucărie care face un zgomot foarte supărător pentru cei din jur. Pentru a scăpa de acest stres, într-o dimineaţă Ionuţ îi ia jucăria lui Florin şi o ascunde în seif. Seiful îl închide cu un cod format din $n$ litere mici ale alfabetului englez. După ce se trezeşte Florin, începe tărăboiul legat de faptul că nu mai găseşte jucăria. După multe discuţii, Ionuţ îi spune lui Florin că jucăria este în seif, dar că nu-şi mai aminteşte codul de deschidere.

Pentru a prelungi perioada de linişte, Ionuţ îi spune lui Florin un cuvânt, format din litere mici ale alfabetului englez, despre care afirmă:

• Codul este scris cu $n$ litere ce se regăsesc în acest cuvânt;
• Literele din cod sunt fie distincte, fie există cel mult o literă care se repetă de exact două ori în cod, dar asta numai dacă litera se găseşte şi în cuvânt pe cel puţin două poziţii.

Acum Florin are mult de lucru, pentru că începe să scrie pe un caiet toate variantele distincte pentru cod, pornind de la indiciile date de Ionuţ.

Cerinţă

Cunoscând numărul de litere al codului $n$ şi cuvântul spus de Ionuţ, determinaţi numărul de coduri scrise de Florin.

Date de intrare

Fişierul de intrare cod.in va conţine pe prima linie numărul $n$, iar pe a doua linie cuvântul spus lui Florin de către Ionuţ.

Date de ieșire

Fişierul de ieşire cod.out va conţine pe prima linie numărul cerut, $\text{mod } 9 \ 901$.

Restricții și precizări

• $1 \leq$ numărul de caractere din cuvânt $\leq 250$
• $1 \leq n \leq 26$
• $k \text{ mod } p$ reprezintă restul împărţirii întregi a lui $k$ la $p$.

Exemplu

cod.in

3
radarr

cod.out

18

Explicație

Codurile posibile pot fi: rad, rda, ard, adr, dra, dar, raa, ara, aar, daa, ada, aad, drr, rdr, rrd, arr, rar, rra.