How to calculate (x^(y^z)) % 1000000007 ?
There is something called Euler totient function using it you can solve it like:
x^(y^z) = x^( (y^z)%PHI(M) ) % M
where PHI(M) is the value for totient function for M. If M is prime then PHI(M) = M-1
so basically you needed to do:
x^(y^z) = x^( (y^z)%1000000006) % 1000000007
I just calculated value of 2^i % 10e9+6 for the question
6 Likes
Any reason for taking M-1.
Because, No will believe that solution was wrong just because of taking M, not M-1.
Well I already told there is something called Euler totient function which helpful to calculate x^(y^z) since while calculation of y^z you cannot take %M since rule is applicable only for addition,multiplication and subtraction and y^z can overflow so you need to take mod somehow. Read the Application mentioned here :Euler's totient function - Algorithms for Competitive Programming
There was a question in a Long contest of Codechef that’s why I know about it.
2 Likes
Thankyou !! 
even if u didn’t know the euler totient function …!!!
This can be done by following intuition …
eg
3^(2^5)=9^(2^4)=81^(2^3) and so on
this can be done in o(n) here n is 5 in the ques n can be upto 10^5 which can easily be done in 1 sec or less.
if u didn’t get ask me again …!!!
Sorry didn’t get you
Can’t we Binary Exponentiaton instead?
i did this power 62 at a time but got only partial credit due to TLE.
We have to do this for each i from 1 to n so this is not feasible.
@all_too_well no this can be …see below
as all the prime no have the same power ,so first iterate from 1 to n and multiply all the prime no .
after first pass u will get a single no (say it’s x ( prod of all prime no from 1 to n))
now only task left is (x^(2^k)) which can be done in o(k) and k <= 100000 ,so this will pass without any TLE.
1 Like
Bro can u explain me plz with some example 
Just a query . Does anyone know when is the finals of codersbit is scheduled . did anyone get any email regarding this ?
I emailed them but as expected no response from their side and they have done lots of controversial things like they said they will organize 40 contest i got to give only 1 and my college got 2 contest .2nd contest for those who missed 1st one and they said top 1000 but from different leaderboard how will they select 
Everyone got only 1 contest and every college got 1 or 2 contest . But they did not inform anything that’s the problem.
2 Likes