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 >

	beet_aizu: 2018-11-15 05:34:28 what "unsigned 32bit integers" means? Isn't that different from POWTOW? =(Francky)==> https://en.wikipedia.org/wiki/32-bit#Range_for_storing_integers Last edit: 2018-11-16 22:40:49
	beet_aizu: 2018-11-14 15:04:24 plz help me (I stucked whole day) #22705069 =(Francky)=> First solve POWTOW Last edit: 2018-11-14 18:21:04
	:D: 2018-09-28 11:25:34 Very good problem, but watch out for border cases. Especially 0^^X it trippy. =(Francky)=> Thanks for your appreciation ;-) Last edit: 2018-09-28 14:46:44
	[Lakshman]: 2014-12-31 15:44:25 Finally AC.:) Thanks @ Francky for such an awesome problem . It took me one month to find the last corner case. --ans(Francky)--> Well done, we can say it is the power of totient! ;-) Last edit: 2014-12-31 16:03:05
	[Lakshman]: 2014-11-23 20:38:56 @Francky My last submission covers all possible cases but still WA, Really hard to get those cases. --ans(Francky)--> Based on last code (12961488), you should have checked more small cases. You have WA for small cases like 0 0 2, or 5 0 3, and many others... good luck. Last edit: 2014-11-23 20:57:48
	fitcat: 2014-11-22 01:39:00 @Francky: This is my 2nd AC problem from you. Enjoyed solving it, too. Thanks. --ans--> You're welcome. Last edit: 2014-11-22 10:32:49
	S.Y.P.Lai: 2014-11-18 04:18:08 @Francky - I have created a post in the forum. Please have a look when you have time. Thank you! --ans(Francky)--> Done. @Francky - Thank you! Finally isolated the large prime factor problem. Last edit: 2014-11-18 08:26:52
	[Lakshman]: 2014-11-17 16:38:08 @Francky Can you please tell if my approach is correct? --ans(Francky)--> The heart of the problem is your "solve" function, it will be much complex than that... It is strongly recommended to solve POWTOW first. --Lakshman--> Now I made some changes but getting WA any suggestion about WA. Thanks --Francky--> I didn't saw your comment before... sorry for late answer. For the answer, just follow previous indications : you should check with a brute force for all possible small values, you will have surprises. Last edit: 2014-11-19 09:15:00
	S.Y.P.Lai: 2014-11-17 14:26:31 @Francky Sorry, I can't catch the 2^^2 = 4 problem. Which versions of my code you have checked? I usually mix up the code when I keep changing, re-submitting and then disqualifying after WA. 2 2 1 = 0 2 2 2 = 0 2 2 3 = 1 2 2 4 = 0 2 2 5 = 4 ... 2 2 m = 4 ... 2 2 4294967295 = 4 I can't test each m, but I have tested at least the first 100 and some other extreme values. --ans(Francky)--> I've only checked 12914151, your last submission at the time of my test. It's true the previous one doesn't have this issue, nor the new ones. If you need help to build a Python simple checker, with pleasure I'll answer in forum python section after you post your draft for that. @Francky - Thankyou for the clarification. In the version you have checked, I removed a while loop. That's the reason for the 2^^2 problem. Last edit: 2014-11-17 15:16:17
	Francky: 2014-11-17 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.

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