#include <bits/stdc++.h>
using namespace std;

long long n, mod, k;

struct matrix{
	long long a[5][5] = {};
	int n, m;
	friend matrix operator*(matrix a, matrix b){
		matrix c;
		c.n = a.n;
		c.m = b.m;
		for(int i = 1; i <= c.n; i++){
			for(int j = 1; j <= c.m; j++){
				for(int k = 1; k <= a.m; k++){
					c.a[i][j] += a.a[i][k] * b.a[k][j];
					c.a[i][j] %= mod;
				}
			}
		}
		return c;
	}
}a, c;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> mod >> k >> n;
	a.n = a.m = c.n = c.m = 2;
	k %= mod;
	a.a[1][1] = k;
	a.a[1][2] = -1;
	a.a[2][1] = c.a[1][1] = c.a[2][2] = 1;
	if(!n){
		cout << 2 << endl;
		return 0;
	}else if(n == 1){
		cout << k << endl;
		return 0;
	}
	n -= 1;
	while(n){
		if(n & 1) c = c * a;
		a = a * a;
		n >>= 1;
	}
	cout << (c.a[2][1] * (k * k - 2) + c.a[2][2] * k + mod * 100000000) % mod << endl;
	return 0;
}