答案（包正确）

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
typedef long long ll;

ll p;

struct Matrix {
ll a[3][3];
Matrix() {
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
a[i][j] = 0;
}
Matrix operator*(const Matrix& other) const {
Matrix res;
for (int i = 0; i < 3; ++i)
for (int k = 0; k < 3; ++k)
if (a[i][k])
for (int j = 0; j < 3; ++j)
res.a[i][j] = (res.a[i][j] + a[i][k] * other.a[k][j]) % p;
return res;
}
};

Matrix mat_pow(Matrix base, ll exp) {
Matrix res;
for (int i = 0; i < 3; ++i) res.a[i][i] = 1;
while (exp) {
if (exp & 1) res = res * base;
base = base * base;
exp >>= 1;
}
return res;
}

int main() {
ll n, k;
cin >> n >> k >> p;
if (n == 1 || n == 2) {
cout << 1 % p << endl;
return 0;
}

// 状态：(prev_modk, cur_modk) ）
unordered_map<ll, ll> state_map;
vector<ll> month_fp;   
vector<ll> month_delta; 
month_fp.push_back(0); 
month_fp.push_back(1 % p);
month_fp.push_back(1 % p);
month_delta.push_back(0); 
month_delta.push_back(0);
month_delta.push_back(0);

ll a_k = 1, b_k = 1;   
ll a_p = 1 % p, b_p = 1 % p;
ll cur_month = 2;
state_map[1 * k + 1] = 2;

ll start = -1, cycle_len = -1;

while (true) {
    cur_month++;
    ll sum_k = (a_k + b_k) % k;
    ll delta = (sum_k == 1) ? 1 : 0;
    ll c_k = (sum_k - delta + k) % k;
    ll c_p = (a_p + b_p - delta) % p;
    if (c_p < 0) c_p += p;

    month_fp.push_back(c_p);
    month_delta.push_back(delta);

    ll state = b_k * k + c_k;
    auto it = state_map.find(state);
    if (it != state_map.end()) {
        start = it->second;
        cycle_len = cur_month - start;
        break;
    }
    state_map[state] = cur_month;

    a_k = b_k; b_k = c_k;
    a_p = b_p; b_p = c_p;
}

// 如果 n 在循环开始之前
if (n <= cur_month) {
    cout << month_fp[n] << endl;
    return 0;
}


Matrix total;
for (int i = 0; i < 3; ++i) total.a[i][i] = 1;
for (ll t = start + 1; t <= start + cycle_len; ++t) {
    Matrix M;
    M.a[0][0] = 1; M.a[0][1] = 1; M.a[0][2] = (p - month_delta[t]) % p;
    M.a[1][0] = 1;
    M.a[2][2] = 1;
    total = M * total;   
}

ll full_cycles = (n - start) / cycle_len;
ll rem = (n - start) % cycle_len;

Matrix power = mat_pow(total, full_cycles);


ll f_start = month_fp[start];
ll f_prev = month_fp[start - 1];
ll vec[3] = {f_start, f_prev, 1};

ll new_vec[3] = {0};
for (int i = 0; i < 3; ++i)
    for (int j = 0; j < 3; ++j)
        new_vec[i] = (new_vec[i] + power.a[i][j] * vec[j]) % p;


for (ll t = start + 1; t <= start + rem; ++t) {
    ll new_f = (new_vec[0] + new_vec[1] - month_delta[t]) % p;
    if (new_f < 0) new_f += p;
    new_vec[2] = 1;
    new_vec[1] = new_vec[0];
    new_vec[0] = new_f;
}

cout << new_vec[0] << endl;

}