import java.math.BigInteger;
import java.util.Scanner;

import static java.lang.System.exit;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n=scanner.nextLong();
        long m=scanner.nextLong();
        BigInteger p = scanner.nextBigInteger();
        long ouler=m;
        long temp = m;
        for(long i=2;i*i<=temp;i++){
            if(temp%i==0){
                ouler=(ouler/i)*(i-1);
                while(temp%i==0){
                    temp/=i;
                }
            }
        }
        if(temp>1){
            ouler=(ouler/temp)*(temp-1);
        }
        String str = String.valueOf(ouler);
        BigInteger t = new BigInteger(str);
        if(p.compareTo(t)>=0){
            p=p.mod(t);
            p=p.add(t);
            long pw  = p.longValue();
            long ans = quickpow(n,pw,m);
            System.out.println(ans);
        }else{
            long pw = p.longValue();
            long ans = quickpow(n,pw,m);
            System.out.println(ans);
        }

    }

    private static long quickpow(long n, long pw, long m) {
        long ans = 1;
        n = n%m;
        while(pw>0){
            if(pw%2==1){
                ans=(ans*n)%m;
            }
            n=(n*n)%m;
            pw/=2;
        }
        return ans;
    }
}