Fişierul intrare/ieşire:	calcul.in, calcul.out	Sursă	preONI 2006 Runda 4
Autor	Mircea Bogdan Pasoi	Adăugată de
Timp execuţie pe test	0.2 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	4/5

Vezi solutiile trimise | Statistici

Calcul

Bronzarel a crescut mare si in curand va merge la facultate. Totusi, admiterea la facultate nu este asa de simpla, avand probe dificile precum matematica. Ca sa se pregateasca, Bronzarel lucreaza zilnic la matematica, efectuand diverse calcule. Zaharel vrea sa-i arate lui Bronzarel ca poate rezolva orice problema de matematica cu ajutorul calculatorului si a indemanarii lui de programator, si i-a cerut acestuia sa-i dea sa rezolve cea mai grea problema pe care o stie! Bronzarel a scris imediat pe o foaie de hartie urmatoarea suma:
S(A,B) = A¹ + A² + A³ + ... A^B
si i-a spus ca trebuie doar sa calculeze valoarea ei. Fiindca rezultatul poate fi un numar foarte mare, Bronzarel se multumeste daca Zaharel determina doar ultimele C cifre ale sumei.

Cerinta

Imaginati-va ca sunteti in locul lui Zaharel si scrieti programul care ii va arata lui Bronzarel ca problemele dificile de matematica pot fi rezolvate cu ajutorul calculatorului!

Date de Intrare

Prima linie a fisierului calcul.in va contine numarul natural A, in baza 10. A doua linie va contine numarul natural B, care va fi dat in baza 16, iar a treia linie va contine numarul natural C.

Date de Iesire

Prima linie a fisierului calcul.out va contine ultimele C cifre ale sumei mentionate mai sus.

Restrictii si observatii

• 0 ≤ A ≤ 10^100.000
• 1 ≤ B ≤ 16^50.000
• 1 ≤ C ≤ 9
• Cifrele in baza 16 sunt 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F (doar majuscule)
• Pentru 20% din teste A ≤ 10⁹ si B ≤ 16⁴
• Pentru 60% din teste B ≤ 16^1.000
• Pentru 50% din teste cmmdc(A-1, 10^C)=1

Exemple

Explicatii

2¹ + 2² + 2³ + 2⁴ + 2⁵ + 2⁶ + 2⁷ = 254

Explicatii

47¹+47²+47³+47⁴+47⁵+47⁶+47⁷+47⁸+47⁹+47¹⁰+47¹¹+47¹² = 118.717.384.915.664.851.680

Cum se trimit solutii?