Bijuterie

Maria Antoaneta a fost o figură controversată în istoria Franței, devenind soția Regelui Ludovic al XVI-lea la data de 16 mai 1770. Regina era un cititor pasionat de romane istorice și interesul său științific a determinat-o să asiste la lansarea de baloane cu aer cald. Ea a fost fascinată de filosofia lui Rousseau precum și de cultura incașilor din Peru, de cultul lor pentru soare. Pe de altă parte, tânăra delfină era pasionată de rochii și bijuterii. Afacerea Colierul Reginei a fost un scandal de mare amploare. Unui mare bijuterier austriac i s-a dat sarcina de a dezmembra bijuteriile coroanei pentru a crea o bijuterie și mai valoroasă și frumoasă. Acesta știe valoarea bijuteriei pe care trebuie să o dezmembreze, care poate fi de ordinul milioanelor. Valoarea este un număr întreg $N$ cu $K$ cifre. Pentru că bijuterierul este foarte talentat și cunoaște valoarea pieței, știm că a estimat corect prețul $N$ și acesta nu începe cu cifre de $0$. Ca să își îndeplinească datoria, el dorește să știe toate modurile în care poate obține o bijuterie cu o valoare strict mai mare decât $N$. El a definit $B(N)$ ca fiind numărul de numere întregi strict mai mari decât $N$, care se formează prin permutarea cifrelor lui $N$.

Cerință

Cunoscând $K$ și $N$, să se determine $B(N)$.

Date de intrare

Fișierul de intrare bijuterie.in conține pe prima linie numărul natural $K$ iar pe a doua linie $K$ cifre reprezentând, în ordine, cifrele numărului $N$.

Date de ieșire

Fișierul de ieșire bijuterie.out va conține pe prima linie valoarea lui $B(N)$. Deoarece această valoare poate fi foarte mare, să se afișeze rezultatul modulo $1\ 000\ 000\ 007$.

Restricții și precizări

• $1 \leq K \leq 1\ 000\ 000$
• Se garantează că numărul $N$ nu începe cu cifre de $0$.

Exemplul 1

bijuterie.in

2
15

bijuterie.out

1

Exemplul 2

bijuterie.in

4
1123

bijuterie.out

11