A nagy maradékszámítás

Számítsd ki az R = B^P mod M értékét nagy B, P és M esetén, hatékony algoritmust használva! (Így van, ennél a feladatnál szigorú időkorlát van!)

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. Minden teszteset három (soronként egy-egy) egész számból áll, B, P, M sorrendben. B és P a [0; 2 147 483 647] zárt intervallumba esnek, míg M az [1; 46 340] zárt intervallumba esik. Az egymást követő teszteseteket egy-egy üres sor választja el egymástól. A bemenetet az állományvégjel (EOF) zárja.

A kimenet specifikációja

Minden tesztesetre egy sort kell a kimenetre írni, amely egyetlen egész számot, a művelet eredményét tartalmazza.

Példa bemenet

1. 3
2. 18132
3. 17
5. 17
6. 1765
7. 3
9. 2374859
10. 3029382
11. 36123

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 13
2. 2
3. 13195

letöltés szöveges állományként