MTETRA  Modular Tetration
The ordinary arithmetical operations of addition, multiplication and exponentiation are naturally extended into a sequence of hyperoperations as follows.
3×7 = 3 + 3 + 3 + 3 + 3 + 3 + 3 ; there are 7 copies of "3" 3^7 = 3 × 3 × 3 × 3 × 3 × 3 × 3 ; there are 7 copies of "3" 3^^7 = (3^(3^(3^(3^(3^(3^3)))))) ; there are 7 copies of "3"
To extend the sequence of operations beyond exponentiation, Knuth defined a “double arrow” operator to denote iterated exponentiation (tetration) ^^ in ASCII notation.
This gives us some very big numbers, your task will be to compute modular tetration.
X^0=1 for all X, as an empty product.
X^^0=1 for all X, for similar reason.
Input
The first line of input contains an integer
T, the number of test cases.
On each of the next T lines, your are given
three integers X, N, and M.
Output
For each test case, you have to print X^^N modulo M.
Example
Input: 3 3 2 20 3 3 345 993306745 75707320 1000000000
Output: 7 312 884765625
Constraints
0 < T <= 10^4 X, N, M unsigned 32bit integers 1 < M
Explanations
3^^2 = 3^3 = 27 = 7 [mod 20] 3^^3 = 3^(3^3) = 3^27 = 7625597484987 = 312 [mod 345]
Problem designed to be solvable using some 'slow' languages like Python, under half the time limit. (20170211 : TL updated ; compiler changes)
It is recommended to solve first Power Tower City.
;) Have fun.
hide comments
S.Y.P.Lai:
20141117 03:15:04
Its looks like some test cases having "m" with large prime factors. I need to write a faster implementation of Euler's totient (phi) function.


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20140901 11:47:27
@Francky: Thanks for your reply, found some error on my code/formula after compared it with python bruteforce, now my new code handled that case correctly, but I'm still getting WA, your test case is very strong, I don't know what's wrong on my code now, I've compared my new code with python bruteforce on reasonable small case, but I found nothing wrong..


Francky:
20140831 10:09:52
@tjandra : I can't tell anything about POWTOW, I didn't optimize it nor find some weakness, even I used slow IO...


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20140825 07:26:03
My AC solution on POWTOW getting WA here, there are two possibilities, this problem has wrong test case, or that problem have weak test case.. 

Stilwell:
20140515 01:54:48
What's the answer of 0^^1 and 0^^2


Min_25:
20140506 12:47:59
@Francky


Robert Gerbicz:
20140505 17:43:59
For (...snip...) is the correct form?


Francky:
20140505 10:14:44
Congratulations to Min_25 as the first solver ; good job. Last edit: 20140505 11:18:14 
Added by:  Francky 
Date:  20140504 
Time limit:  1.200s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem 