Fişierul intrare/ieşire:	guinness.in, guinness.out	Sursă	Concursul National de Informatica "Adolescent Grigore Moisil" 18
Autor	Teodor Ionescu	Adăugată de	AGMInformatica •AGMinformatica
Timp execuţie pe test	0.5 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Guinness

A fost odată ca niciodată; că de n-ar fi, nu s-ar mai povesti
de când coda bunicul şmene şi comisia minciunele
de când se băteau ruşii în evaluatoare
de când se luau de gât concurenţii cu borderoul de se sărutau, înfrăţindu-se
de când se potcovea o.e.i.s. la un picior cu douăzeci şi trei de oca de blat şi s-arunca în slava cerului de ne aducea probleme

În vremea aceea, pe când lumea era sub stăpânirea malefică a feluritelor structuri de date, trăia pe pământ Făt-Frumos Tatăl, proaspăt pensionar.
Acesta avea 3 frumoşi. Pe frumosul mare şi pe cel mijlociu deja i-am cunoscut în problema Staropramen şi putem uşor deduce de ce au picat testul tatălui lor atunci când acesta s-a deghizat într-o problemă complicată pentru a-i speria.

Norocul de a moşteni împărăţia lui Homeless-Împărat a revenit astfel micului frumos.
Zis şi făcut. Mezinul încalecă pe armăsarul sau fermecat cu Treap-în-Frunte, căruia îi dăduse să mănânce nişte constante în prealabil, şi porneşte la drum.

După multe zile de drumeţie ajunge într-o pădure de arbori din care nu ştia cum să mai iasă şi în care îl întâlneşte pe Ţiganul Algoritmist. Deşi taică-său îl avertizase că ăsta umblă cu formule, micul frumos acceptă provocarea acestuia de a ridica un număr A la puterea B şi a-l afişa modulo M.

Date de intrare

Fişierul de intrare guinness.in conţine pe prima linie numarul T. Urmatoarele T linii descriu fiecare test în parte în formatul A B M.

Date de ieşire

În fişierul de ieşire guinness.out veţi afişa raspunsul la cerinţele Ţiganului Algoritmist.

Restricţii

• 1 ≤ T ≤ 10
• 0 ≤ A ≤ 10⁹
• 1 ≤ B ≤ 10^100.000
• 1 ≤ M ≤ 10⁹

• Personajele poveştii sunt inspirate din viaţa reală
• F-F-Tatăl are o viziune neconvenţională asupra pensionării

Exemplu

Cum se trimit solutii?