Fișierul intrare/ieșire	rest.in, rest.out	Sursă	Olimpiada locala 2014, Clasa a 5-a
Autor	autor necunoscut	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	1 sec	Limită de memorie	1024 KB
Scorul tău	N/A	Dificultate	4

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Rest (clasa a 5-a)

Andrei, mare pasionat de matematică, compune adesea probleme cu numere mari: fie N un număr natural care poate avea maxim 100 000 de cifre în scrierea în baza 10, pe un astfel de număr se definește prefix al lui N ca fiind un număr format din primele cifre ale lui N, în ordine de la stânga la dreapta. Prefixul poate avea minim o cifră și maxim tot atâtea cifre ca N. Restul modulo K al unui număr natural este restul obținut la împărțirea întreagă a acelui număr la K.

Cerință

Ajutați-l pe Andrei sa rezolve următoarea problemă: considerând resturile modulo K ale tuturor prefixelor lui N, determinați care este restul maxim care apare și pentru câte dintre aceste prefixe se obține.

Date de intrare

Fișierul de intrare rest.in conține pe prima linie numărul natural K, iar pe a doua linie un șir de cifre, despărțite printr-un spațiu, reprezentând cifrele numărului natural N.

Date de ieșire

Fișierul de ieșire rest.out va conține pe prima linie două numere naturale r nr, despărțite printr-un spațiu, reprezentând restul maxim modulo K determinat și numărul de prefixe pentru care se obține acest rest.

Restricții

• 1 ≤ K ≤ 100
• 1 ≤ numărul de cifre ale lui N ≤ 100 000

Exemplu