\(M\) の制約が大きいので，ループで周期を見つける方法は無理． 実際， \(M\) が素数のとき，周期の長さが \(M-1\) になるケースがある．
そこで最初考えたのは，等比数列の和の公式を使って，分母が \(M\) と互いに素な 場合に帰着させようとしたが出来なかった．
公式解説
漸化式が線形なので，行列累乗をダブリングで求める．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
using M = vvll;
M prd_mod(M a, M b, ll mod){
M c;
c.resize(2);
rep(i,2) c[i].resize(2);
rep(i,2) rep(j,2) {
ll x = 0;
rep(k,2){
x += a[i][k] * b[k][j];
x %= mod;
}
c[i][j] = x;
}
return c;
}
int main() {
ll a,x,m; cin >> a >> x >> m;
vvll p = {
{a,0},
{1,1}
};
// p^2^i
vvll q = {
{1,0},
{0,1}
};
while(x){
if(x&1){
q = prd_mod(q, p, m);
}
p = prd_mod(p, p, m);
x >>= 1;
}
cout << q[1][0] << endl;
return 0;
}
