#include<bits/stdc++.h>

#define LL long long

using namespace std;

const int MAXN = 1e7 + ;

const int mod  = 1e9 + ;

bool check[MAXN];

int phi[MAXN], prime[MAXN], tot;

LL sum[MAXN],now[MAXN];

LL myPow(LL a, int p, LL mod){

    LL ret = ;

    while(p){

        if(p & ) ret = ret * a % mod;

        a = a * a % mod;

        p >>= ;

    }

    return ret;

}

void phi_and_prime_table(int N) {

    memset(check,false,sizeof(check));

    phi[] = ;

    tot = ;

    for(int i = ; i <= N; i++) {

        if( !check[i] ) {

            prime[tot++] = i;

            phi[i] = i - ;

        }

        for(int j = ; j < tot; j++) {

            if(i * prime[j] > N)

                break;

            check[i * prime[j]] = true;

            if( i % prime[j] == ) {

                phi[i * prime[j]] = phi[i] * prime[j];

                break;

            } else {

                phi[i * prime[j]] = phi[i] * (prime[j] - );

            }

        }

    }

    for(int i = ; i <= N; i ++){

        sum[i] =  (sum[i - ] + phi[i]) % mod;

    }

}

LL S(int n, int m){

    if( n ==  ) return sum[m];

    if( m ==  ) return ;

    for(int i = ; i < tot && prime[i] <= n; i ++){

        if( n % prime[i] ==  ) {

            int p = prime[i];

            return (( 1LL * (p - ) * S(n/p, m))%mod + S(n, m/p) % mod ) % mod;

        }

    }

}

LL A(int k,int p){

    if(k == ) return ;

    if(p == ) return ;

    return myPow(k, phi[p] + A(k, phi[p]), p);

}

int main() {

    phi_and_prime_table();

    int n,m,p;

    while(~scanf("%d%d%d",&n,&m,&p)){

        int k = S(n,m);

        printf("%lld\n",A(k, p));

    }

    return ;

}