SPOJ.com - Problem MTETRA

MTETRA - Modular Tetration

no tags

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. (2017-02-11 : TL updated ; compiler changes)
It is recommended to solve first Power Tower City.
;-) Have fun.

Submit solution!

hide comments

< Previous 1 2 Next >

	S.Y.P.Lai: 2014-11-17 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. Now, I run into the same situation as Tjandra! Already discovered a handful of problems not being caught by POWTOW and fixed, still WA. I am not familiar with python. The example python brute force code found from Google produces much more problems than my code. How can I find the corner cases? --ans(Francky)--> You have only few WA. To find corner cases, I see two solutions. 1) Math check of the whole method. AND/OR 2) brute force all reasonable triples X,N,M, firstly with N=1, then N=2, then N=3 (for the few reasonable possible semi-brute check). With Python, you can use Y=XX (computed once), and make a loop on various M that compute pow(X, Y, M) to check N=2. I quickly saw in you answers a WA with N=8, but I'm quite sure another WA could happen with a much lower N (2 or 3). If I find some time, I'll check that assert. Hope that can help, good luck. You can use the forum section, in Python, I'll help you to build your Python checker if you want. You're not so far. Last edit: 2014-11-17 10:31:44**
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2014-09-01 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.. --ans(Francky)--> It's true, now for small cases, our results match, but not for some other cases. You'll be able to find some cases ; good luck ;-) Last edit: 2014-09-01 19:44:10
	Francky: 2014-08-31 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... About your code here, you should check vs brute force on some small example, you will have surprises, eg : 2 3 m is equal to 16 mod m, your program output wrong results. You're not so far, good luck. (I think I put some hard cases, as usual, but there's no vicious cases for that problem, imho) Last edit: 2014-08-31 10:11:45
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2014-08-25 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: 2014-05-15 01:54:48 What's the answer of 0^^1 and 0^^2 --ans(Francky)--> x^^1 = x (by definition, so 0^^1 = 0), 0^^2 = 0^0 = 1 (given in description) Last edit: 2014-05-15 09:14:51
	Min_25: 2014-05-06 12:47:59 @Francky Thank you.
	Robert Gerbicz: 2014-05-05 17:43:59 For (...snip...) is the correct form? (gerrob) Yes! --ans(Francky)--> Well done. I'll add X^^0=X^0=1 in description ; congrats to you too. (gerrob) OK, and thanks. Last edit: 2014-05-05 17:45:02
	Francky: 2014-05-05 10:14:44 Congratulations to Min_25 as the first solver ; good job. Last edit: 2014-05-05 11:18:14

Submit solution!

Added by:	Francky
Date:	2014-05-04
Time limit:	1.200s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Own Problem