Given two numbers n and m, evaluate the infinite power tower:
n^(n+1)^(n+2)^(n+3)^(n+4)^... mod m
Keep in mind that ^ is right-associative. So 2^3^4 = 2^(3^4). Now how can you possibly assign a value to an infinite sequence of right-associative operators?
Define f(n,m,i) as the power tower containing the first i terms of the infinite power tower. Then there is some constant C such that for every i > C, f(n,m,i) = f(n,m,C). So you could say the infinite power tower converges on a certain value. We're interested in that value.
Your program must be able to compute n = 2017, m = 10^10 in under 10 seconds on a reasonable modern PC. That is, you should implement an actual algorithm, no bruteforcing.
You may assume that n < 230 and m < 250 for the numerical limits in your programming language, but your algorithm must theoretically work for any size n, m. However your program must be correct for inputs within these size limits, intermediate value overflows are not excused if the inputs are within these limits.
2, 10^15 566088170340352 4, 3^20 4 32, 524287 16