#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define ll long long
#define endl "\n"
#define S second
#define F first
#define ln cout<<endl;
#define mem(a) memset((a),0,sizeof (a));
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define debug cout<<"here!"<<endl;
#define int long long
ll cnt,n,m,t,ans,ant;
const int N=2e5+10;
const int INF=0x3f3f3f3f;
string str;
int p,k,tt;
ll fastpower(int base,int power,int mod)
{
	int ans=1;
	while(power)
	{
		if(power&1)
		{
			ans=ans*base;
			if(ans<0)
			{
				int tmp=-ans;
				int num=tmp/p;
				ans+=p*(num+1);
				ans%=p;
			}
		}
		power>>=1;
		base=base*base%p;
	}
	return ans;
}
void solve()
{
	
//	cout<<fastpower(3,23,1000000000000000);
	cin>>p>>k>>tt;
	int ans=fastpower(-k,tt,p)%p;
	cout<<ans<<endl;
	
	return;
}

signed main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	ll _=1;
//	cin>>_;
	while(_--)
		solve();
	return 0;
}