#include <bits/stdc++.h>
using namespace std;
long long n,k,mod;
struct Matrix {
  long long a[3][3];

  Matrix() { memset(a, 0, sizeof a); }

  Matrix operator*(const Matrix &b) const {
    Matrix res;
    for (register int i = 1; i <= 2; ++i)
      for (register int j = 1; j <= 2; ++j)
        for (register int k = 1; k <= 2; ++k)
          res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % mod;
    return res;
  }
} ans, base;

inline void init() {
  base.a[1][1] = k;
  base.a[1][2] = 1;
  base.a[2][1] =-1;
  ans.a[1][1] = (k*k-2)%mod;
  ans.a[1][2] = k%mod;
}

inline void qpow(long long b) {
  while (b) {
    if (b & 1) ans = ans * base;
    base = base * base;
    b >>= 1;
  }
}
long long read(){
    long long a=0;int op=1;char ch=getchar();
    while(ch<'0'||'9'<ch){if(ch=='-')op=-1;ch=getchar();}
    while('0'<=ch&&ch<='9'){a=(a<<3)+(a<<1)+(48^ch);ch=getchar();}
    return a*op;
}
int main() {
  mod=read();
  k=read();
  n=read();
  if (n == 1) {
  	printf("%lld",k%mod);
  	return 0;
  }
  if (n == 2) {
  	printf("%lld",(k*k-2)%mod);
  	return 0;
  }
  init();
  qpow(n - 2);
  printf("%lld",(ans.a[1][1] +mod)% mod);
}