//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=y;x<=z;x++)
#define per(x,y,z) for(ll x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll mod = 3214567;

ll n, m, r;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
ll qpow(ll x, ll y) {
    ll ans = 1;
    for(;y;y>>=1,x=x*x%mod) if(y & 1) ans = ans * x % mod;
    return ans;
}
ll inv(ll x) {return qpow(x, mod-2);}
ll phi(ll x) {
    ll ans = x;
    for(ll i=2;i*i<=x;i++) {
        if(!(x % i)) {
            ans = ans / i * (i - 1);
            while(!(x % i)) x /= i;
        }
    }
    if(x > 1) ans = ans / x * (x - 1);
    return ans;
}

int main() {
    scanf("%lld%lld%lld", &n, &m, &r);
    ll k = 0, lim = sqrt(m);
    rep(d, 1, lim) {
        if(!(m % d)) {
            k = (k + qpow(r, d) * phi(m/d) % mod) % mod;
            if(d != m / d) k = (k + qpow(r, m/d) * phi(d) % mod) % mod;
        }
    }
    k = k * inv(m) % mod;
    ll ans = (qpow(k-1, n) + ((n & 1) ? -1 : 1) * (k - 1) + mod) % mod;
    printf("%lld\n", ans);
    return 0;
}