#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

typedef long long LL;

LL N, K, P;

// 3x3 矩阵结构
struct Matrix {
    LL m[3][3];
    Matrix() { memset(m, 0, sizeof(m)); }
    void init_identity() {
        for (int i = 0; i < 3; i++) m[i][i] = 1;
    }
};

// 矩阵乘法：C = A * B，利用 __int128 防止乘法溢出
Matrix multiply(const Matrix& A, const Matrix& B) {
    Matrix C;
    for (int i = 0; i < 3; i++) {
        for (int k = 0; k < 3; k++) {
            if (!A.m[i][k]) continue;
            for (int j = 0; j < 3; j++) {
                LL prod = (LL)((__int128)A.m[i][k] * B.m[k][j] % P);
                C.m[i][j] = (C.m[i][j] + prod) % P;
            }
        }
    }
    return C;
}

// 矩阵快速幂
Matrix power(Matrix A, LL exp) {
    Matrix res;
    res.init_identity();
    while (exp > 0) {
        if (exp & 1) res = multiply(res, A);
        A = multiply(A, A);
        exp >>= 1;
    }
    return res;
}

// 扩展欧几里得求逆元
LL extgcd(LL a, LL b, LL &x, LL &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    LL d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

LL modInverse(LL a, LL m) {
    if (m <= 1) return -1;
    LL x, y;
    LL g = extgcd(a, m, x, y);
    if (g != 1) return -1;
    return (x % m + m) % m;
}

// 纯斐波那契转移矩阵
Matrix get_pure_fib_matrix(LL len) {
    Matrix base;
    base.m[0][1] = 1;
    base.m[1][0] = 1; base.m[1][1] = 1;
    base.m[2][2] = 1;
    return power(base, len);
}

// 带末尾 -1 重置的段转移矩阵
Matrix get_segment_matrix(LL len) {
    Matrix T = get_pure_fib_matrix(len);
    T.m[1][2] = (T.m[1][2] - 1 + P) % P; // -1 作用于 a_{i+1}
    return T;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> N >> K >> P)) return 0;

    // 1. 特殊边界特判
    if (N == 1 || N == 2) {
        cout << 1 % P << "\n";
        return 0;
    }
    if (K == 1) {
        cout << 0 % P << "\n"; // K=1 时，所有 i>2 的项都会被减 1 变成 0
        return 0;
    }

    // 2. 预处理 Fibonacci 模 K 序列
    vector<LL> fib_val;
    fib_val.push_back(0);        // F_0
    fib_val.push_back(1 % K);    // F_1

    vector<LL> pos(K, -1);
    pos[1 % K] = 1;              // 后续段 k >= 1 首次出现的位置

    LL first_pos_1 = -1;         // 第一段专用：寻找 i > 2 且 F_i = 1 % K
    LL f0 = 0, f1 = 1 % K;

    for (LL i = 2; ; i++) {
        LL f2 = (f0 + f1) % K;
        fib_val.push_back(f2);

        // 允许记录 pos[0] 在内的首次出现位置
        if (pos[f2] == -1) {
            pos[f2] = i;
        }
        // 第一段：寻找 i > 2 且 F_i 模 K 为 1 的位置
        if (i > 2 && f2 == 1 % K && first_pos_1 == -1) {
            first_pos_1 = i;
        }

        f0 = f1;
        f1 = f2;
        if (f0 == 0 && f1 == 1 % K) break; // 皮萨诺周期结束
    }

    LL rem_steps = N - 2; // 从 n=2 推进至 n=N
    Matrix total_trans;
    total_trans.init_identity();

    LL cur_x = 1;

    // 3. 第一段特殊处理 (必须严格满足 i > 2)
    if (first_pos_1 != -1 && (first_pos_1 - 2) <= rem_steps) {
        LL len = first_pos_1 - 2;
        total_trans = multiply(get_segment_matrix(len), total_trans); // 左乘
        rem_steps -= len;
        cur_x = fib_val[first_pos_1 - 1]; // 下一段的起点系数
    } else {
        total_trans = multiply(get_pure_fib_matrix(rem_steps), total_trans);
        rem_steps = 0;
    }

    // 4. 后续段模拟 + 找环加速
    vector<LL> vis(K, -1);
    vector<LL> path_x;
    vector<Matrix> path_mat;
    vector<LL> path_len;
    bool cycle_done = false;

    while (rem_steps > 0) {
        LL inv = modInverse(cur_x, K);
        if (inv == -1 || pos[inv] == -1) {
            total_trans = multiply(get_pure_fib_matrix(rem_steps), total_trans);
            rem_steps = 0;
            break;
        }

        LL len = pos[inv];
        if (len > rem_steps) {
            total_trans = multiply(get_pure_fib_matrix(rem_steps), total_trans);
            rem_steps = 0;
            break;
        }

        // 检侧到环，做周期跨越
        if (!cycle_done && vis[cur_x] != -1) {
            LL start_idx = vis[cur_x];
            LL cycle_steps = 0;
            Matrix cycle_matrix;
            cycle_matrix.init_identity();

            for (size_t i = start_idx; i < path_x.size(); i++) {
                cycle_steps += path_len[i];
                cycle_matrix = multiply(path_mat[i], cycle_matrix); // 左乘累计环矩阵
            }

            // 防除零安全保护
            if (cycle_steps == 0) {
                total_trans = multiply(get_pure_fib_matrix(rem_steps), total_trans);
                rem_steps = 0;
                break;
            }

            LL num_cycles = rem_steps / cycle_steps;
            total_trans = multiply(power(cycle_matrix, num_cycles), total_trans);
            rem_steps %= cycle_steps;
            cycle_done = true;
            continue;
        }

        if (!cycle_done) {
            vis[cur_x] = path_x.size();
            path_x.push_back(cur_x);
        }

        Matrix seg_m = get_segment_matrix(len);
        if (!cycle_done) {
            path_mat.push_back(seg_m);
            path_len.push_back(len);
        }

        total_trans = multiply(seg_m, total_trans);
        rem_steps -= len;
        cur_x = (cur_x * fib_val[len - 1]) % K;
    }

    // 5. 提取答案：V_N = M * [1, 1, 1]^T 的第 1 行（对应 a_N）
    LL ans = (total_trans.m[1][0] + total_trans.m[1][1] + total_trans.m[1][2]) % P;
    cout << (ans + P) % P << "\n";

    return 0;
}