#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
ll p,k,t;

ll mypow(ll a,ll n){
	if(!n)return 1;
	ll tmp = mypow(a,n/2);
	tmp = tmp * tmp%p;
	if(n&1)tmp = tmp*a%p;
	return tmp;
}

int main(){
	cin>>p>>k>>t;

	ll ans = mypow(k,t);

	if(t%2==1)ans = (p - ans)%p;

	cout<<ans<<endl;

    return 0;
}