#include <cstdio>
using namespace std;
inline long long rd() {
    long long ret = 0, flag = 1;
    char c = getchar();
    for (; c > '9' || c < '0'; c = getchar())
        if (c == '-')
            flag = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        ret = ret * 10 + (c - '0');
    return ret * flag;
}
long long mod, k, n;
long long initial[3], a[3][3], ret[3][3];
long long tmp[3][3];
int main() {
    mod = rd();
    k = rd();
    n = rd();
    long long p1 = k, p2 = (k * k - 2) % mod;
    long long p3 = (((k * p2) % mod) - p1) % mod;
    if (n == 0) {
        printf("2\n");
        return 0;
    }
    if (n == 1) {
        printf("%lld\n", p1);
        return 0;
    }
    if (n == 2) {
        printf("%lld\n", p2);
        return 0;
    }
    if (n == 3) {
        printf("%lld\n", p3);
        return 0;
    }
    initial[0] = p3;
    initial[1] = p2;
    initial[2] = p1;
    a[0][0] = k;
    a[1][0] = -1;
    a[0][1] = 1;
    a[1][2] = 1;
    ret[0][0] = k;
    ret[1][0] = -1;
    ret[0][1] = 1;
    ret[1][2] = 1;
    n -= 4;
    while (n) {
        if (n & 1) {
            for (int i = 0; i < 3; ++i) {
                for (int j = 0; j < 3; ++j) {
                    tmp[i][j] = 0ll;
                    for (int k = 0; k < 3; ++k) {
                        tmp[i][j] = (tmp[i][j] + (((__int128_t)a[k][j] * ret[i][k]) % mod)) % mod;
                    }
                }
            }
            for (int i = 0; i < 3; ++i) {
                for (int j = 0; j < 3; ++j) {
                    ret[i][j] = tmp[i][j];
                }
            }
        }
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                tmp[i][j] = 0ll;
                for (int k = 0; k < 3; ++k) {
                    tmp[i][j] = (tmp[i][j] + (((__int128_t)a[k][j] * a[i][k]) % mod)) % mod;
                }
            }
        }
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                a[i][j] = tmp[i][j];
            }
        }
        n >>= 1;
    }
    long long ans = 0ll;
    for (int i = 0; i < 3; ++i) {
        ans = (ans + (((__int128_t)initial[i] * ret[i][0]) % mod)) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}