#include <array>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#define endl '\n'
using LL=long long;

using Mat=array<array<LL,2>,2>;
int p;

Mat mul(Mat x,Mat y) {
    Mat res{};
    for(int i=0;i<2;i++) {
        for(int k=0;k<2;k++) {
            for(int j=0;j<2;j++) {
                res[i][j]=(res[i][j]+(x[i][k]*y[k][j]%p))%p;
            }
        }
    }
    return res;
}

Mat qpow(Mat x,int k) {
    Mat res{};
    res[0][0]=res[1][1]=1;
    while(k) {
        if(k&1) res=mul(res,x);
        k>>=1;
        x=mul(x,x);
    }
    return res;
}

void solve() {
    int k,t;
    cin>>p>>k>>t;
    LL sum1=(LL(p-1)*p/2-k)%p;
    LL sum2=((__int128(p-1)*(p)*(2*(p-1)+1)/6)%p);
    Mat dp{};
    dp[0][0]=0;
    dp[0][1]=-sum2+p;
    dp[1][0]=1;
    dp[1][1]=sum1;
    dp=qpow(dp,t-1);

    Mat res{};
    res[0][0]=1;
    res[0][1]=sum1;
    res=mul(res,dp);
    cout<<res[0][1]<<endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}