How to calculate **(x^(y^z)) % 1000000007** ?

# Codersbit Problem

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

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 :https://cp-algorithms.com/algebra/phi-function.html

There was a question in a Long contest of Codechef thatâ€™s why I know about it.

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.

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.