require 'prime' def phi(n) ps = Array.new Prime.each(n) do |p| ps.push(p) if n % p == 0 end ret = n ps.each do |p| ret *= (1.0 - (1.0/p)) end return ret.round end def modpow(b,e,m) res = 1 while e > 0 if e & 1 == 1 res = (res * b) % m end e >>= 1 b = (b * b) % m end res end def rec(a,n,m) return 1 if n == 0 return 0 if m == 1 m2 = phi(m) b = rec(a,n-1,m2) + m2 return modpow(a,b,m) end a, n, m = gets.split.map(&:to_i) if n == 0 p 1 % m elsif n == 1 p a % m elsif n == 2 p modpow(a,a,m) else p rec(a,p,m) end