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 a, n, m = gets.split.map(&:to_i) if n == 0 puts 1 % m exit end p = a (n % phi(m) - 1).times do p = modpow(a,p,m) end p p % m