Bijuterie

Time limit: 0.08s Memory limit: 256MB Input: bijuterie.in Output: bijuterie.out

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 NN cu KK cifre. Pentru că bijuterierul este foarte talentat și cunoaște valoarea pieței, știm că a estimat corect prețul NN și acesta nu începe cu cifre de 00. 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 NN. El a definit B(N)B(N) ca fiind numărul de numere întregi strict mai mari decât NN, care se formează prin permutarea cifrelor lui NN.

Cerință

Cunoscând KK și NN, să se determine B(N)B(N).

Date de intrare

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

Date de ieșire

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

Restricții și precizări

  • 1K1 000 0001 \leq K \leq 1\ 000\ 000
  • Se garantează că numărul NN nu începe cu cifre de 00.
# Punctaj Restricții
1 11 1K91 \leq K \leq 9
2 22 10K5 00010 \leq K \leq 5\ 000
3 36 5 001K10 0005\ 001 \leq K \leq 10\ 000
4 31 Fără restricții suplimentare

Exemplul 1

bijuterie.in

2
15

bijuterie.out

1

Exemplul 2

bijuterie.in

4
1123

bijuterie.out

11

Log in or sign up to be able to send submissions!