#include<bits/stdc++.h>
#define N 5
#define int long long
using namespace std;
int n,k,mod; 
struct matrix{
	int m[N][N];
}t,l;
matrix times(matrix a,matrix b1){
	matrix c;
	for(int i=1;i<N;i++){
		for(int j=1;j<N;j++){
			c.m[i][j]=0;
		} 
	}
	for(int i=1;i<N;i++){
		for(int j=1;j<N;j++){
			for(int k=1;k<N;k++){
				c.m[i][j]+=a.m[i][k]*b1.m[k][j];
				c.m[i][j]=((c.m[i][j]%mod)+mod)%mod;
			}
		}
	}
	return c; 
}
matrix qpow(matrix a,int p){
	matrix ret;
	for(int i=1;i<N;i++){
		for(int j=1;j<N;j++){
			if(i==j)ret.m[i][j]=1;
			else ret.m[i][j]=0;
		} 
	}
	while(p){
		if(p%2==0){
			a=times(a,a);
			p/=2;
		}
		else{
			ret=times(ret,a);
			p--;
		} 
	}
	return ret;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>mod>>k>>n;
	t.m[1][1]=k;
	t.m[1][2]=-1;
	t.m[2][1]=1;
	t.m[2][2]=0;
	l.m[1][1]=k;
	l.m[2][1]=2;
	if(n<2){
		cout<<l.m[2-n][1];
		return 0;
	}
	matrix b=qpow(t,n-2);
	b=times(b,l);
	cout<<((b.m[1][1]%mod)+mod)%mod;
	return 0;
}

题解里都是矩阵快速幂然后右乘初始矩阵，我的矩阵反过来左乘，同时数据也改变了一下，应该是没问题的。我试了一下，把初始矩阵改成横向的，样例3能过，样例2就过不了了。悬关求助！！！