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
beet_aizu:
20181115 05:34:28
what "unsigned 32bit integers" means? Isn't that different from POWTOW?


beet_aizu:
20181114 15:04:24
plz help me (I stucked whole day) #22705069


:D:
20180928 11:25:34
Very good problem, but watch out for border cases. Especially 0^^X it trippy.


[Lakshman]:
20141231 15:44:25
Finally AC.:) Thanks @ Francky for such an awesome problem . It took me one month to find the last corner case.


[Lakshman]:
20141123 20:38:56
@Francky My last submission covers all possible cases but still WA, Really hard to get those cases.


fitcat:
20141122 01:39:00
@Francky: This is my 2nd AC problem from you. Enjoyed solving it, too. Thanks.


S.Y.P.Lai:
20141118 04:18:08
@Francky  I have created a post in the forum. Please have a look when you have time. Thank you!


[Lakshman]:
20141117 16:38:08
@Francky Can you please tell if my approach is correct?


S.Y.P.Lai:
20141117 14:26:31
@Francky


Francky:
20141117 11:03:13
@S.Y.P.Lai : you could have done a quick check for small input too, MTETRA(2, 2, m) is equal to 4%m, you will have surprise with some small moduli. 
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 