Anagramma

Dotam vārdam $V$ par tā anagrammām sauc visus vārdus, kas iegūti no $V$ burtiem, visus tos saliekot kaut kādā secībā. Atšķirībā no reālās dzīves, arī bezjēdzīgus burtu virknējumus uzskatīsim par derīgām anagrammām. Ievērsiet, ka pats vārds $V$ arī ir viena no $V$ anagrammām. Uzrakstīsim visas $V$ anagrammas pēc kārtas leksikogrāfiskā secībā (vārds $X$ leksikogrāfiskā secībā atrodas pirms vārda $Y$, ja pirmais atšķirīgais burts pēc kārtas vārdā $X$ alfabētā atrodas pirms atbilstošā vietā esošā burta vārdā $Y$) un meklēsim šajā sarakstā doto vārdu $V$.

Piemēram, ja $V$ ir "suns", tad visas tā anagrammas leksikogrāfiskā secībā ir:

nssu, nsus, nuss, snsu, snus, ssnu, ssun, suns, susn, unss, usns, ussn

un vārds “suns” šajā virknē ir astotais pēc kārtas.

Uzrakstiet datorprogrammu, kas dotam vārdam nosaka, kurš pēc kārtas tas ir savu leksikogrāfiski sakārtoto anagrammu sarakstā!

Pirmajā rindā dota naturāla skaitļa $N$ (vārda garums, $N \leq 10^5$) vērtība.

Otrajā rindā dots vārds – $N$ latviešu alfabēta mazo burtu bez diakritiskajām zīmēm virkne.

Izvaddatu vienīgajā rindā jābūt naturālam skaitlim – dotā vārda kārtas numuram leksikogrāfiski sakārtotā tā anagrammu sarakstā. Kārtas numurs jāizvada pēc moduļa $10^9+7$. Izvadīšanai pēc moduļa nav nekāda cita nozīme, kā vien samazināt izvadāmā skaitļa lielumu.