#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long ll;
const int KR = 1e6 + 10, SZ = 3;

ll n, k, P;
ll kcnt = 0;
ll f[6 * KR], len[KR], seq[KR], vis[KR]; 
// f[i] 代表斐波那契第 i 位，len[i] 代表以 i 为开头的段的长度，seq 中存储所有段的开头，vis[i] 记录 i 作为开头的位置。
bool flag;

ll GCD(ll a, ll b) { // 由于还要判断是否存在逆元（互质），因此还需要一个朴素的GCD。
    if (!b) return a;
    return GCD(b, a % b);
}

void exGCD(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return;
    }
    exGCD(b, a % b, x, y);
    ll t = x;
    x = y;
    y = t - a / b * y;
}

ll getInv(ll a, ll P) {
    if (GCD(a, P) != 1) return -1; // 不互质，无逆元。
    ll x, y;
    exGCD(a, P, x, y);
    return (x % P + P) % P;
}

struct Matrix {
    ll o[SZ + 1][SZ + 1];

    Matrix() {
        memset(o, 0, sizeof(o));
    }

    Matrix operator * (const Matrix &x) const {
        Matrix ret;
        for (int i = 1; i <= SZ; i++)
            for (int j = 1; j <= SZ; j++)
                for (int k = 1; k <= SZ; k++)
                    ret.o[i][j] = (ret.o[i][j] + o[i][k] * x.o[k][j] + P) % P;
        return ret;
    }
} mat, tr1, tr2, tr;

Matrix quickPower(Matrix a, ll b) {
    Matrix ret;
    for (int i = 1; i <= SZ; i++) ret.o[i][i] = 1;

    while (b) {
        if (b & 1) ret = ret * a;
        a = a * a;
        b >>= 1;
    }
    return ret;
}

int main()
{
    scanf("%lld%lld%lld", &n, &k, &P);

    if (n == 1 || n == 2) {
        printf("1\n");
        return 0;
    }

    memset(len, 999999, sizeof(len));
    f[1] = f[2] = 1;

    for (ll i = 3; ; i++) {
        f[i] = (f[i - 1] + f[i - 2]) % k;
        if (f[i] % k == 1 && len[1] > 1e18) len[1] = i; // 需要特殊计算 1 开头的长度
        if (f[i] == 1 && f[i - 1] == 1) break;

        ll inv = getInv(f[i], k);
        if (inv != -1) len[inv % k] = min(len[inv % k], i);
    }

    ll now = 1, tot = 0;
    while (1) {
        seq[++kcnt] = now;
        vis[now] = kcnt;
        if (len[now] > 1e18) { // 如果没有逆元
            for (int i = 1; i < kcnt; i++) tot += len[seq[i]]; // 计算之前段的总长
            flag = 1;
            break;
        }

        now = (now * f[len[now] - 1]) % k;
        if (vis[now]) { // 这个数之前出现过，发现循环节
            for (int i = 1; i < vis[now]; i++) tot += len[seq[i]]; // 计算循环节之前段的总长
            break;
        }
    }

    mat.o[1][1] = mat.o[1][3] = 1;
    tr1.o[1][1] = tr1.o[1][2] = tr1.o[2][1] = tr1.o[3][3] = 1;
    tr2.o[1][1] = tr2.o[1][2] = tr2.o[2][1] = tr2.o[3][3] = 1;
    tr2.o[3][1] = -1;

    if (n <= tot) { // 要特别判断如果 n 在无逆元序列 / 循环节之前的情况（两个样例都是这种情况），暴力一段一段算
        len[1]--; // 初始已经算出了 F[1]，因此第一段的长度要 -1 ，n 随之也 -1
        n--;
        for (int i = 1; i < vis[now]; i++) {
            if (n >= len[seq[i]]) { // 假设 n 还够完整的一段，直接矩阵快速幂
                mat = mat * quickPower(tr1, len[seq[i]] - 1) * tr2; 
                n -= len[seq[i]];
            } else { // 否则暴力乘
                mat = mat * quickPower(tr1, n);
                printf("%lld\n", mat.o[1][1]);
                return 0;
            }
        }
    } else {
        len[1]--;
        n -= tot;

        for (int i = 1; i < vis[now]; i++) mat = mat * quickPower(tr1, len[seq[i]] - 1) * tr2; // 此处要计算出进入循环节前的状态

        if (flag) { // 无逆元情况，直接用 tr1 快速幂
            mat = mat * quickPower(tr1, n);
            printf("%lld\n", mat.o[1][1]);
        } else {
            ll loopLen = 0;
            for (ll i = 1; i <= SZ; i++) tr.o[i][i] = 1;
            for (ll i = vis[now]; i <= kcnt; i++) { // 否则计算循环节的总转移矩阵 tr
                tr = tr * quickPower(tr1, len[seq[i]] - 1) * tr2;
                loopLen += len[seq[i]];
            }
            ll tmp = n / loopLen; // 算一下 n 中有几个完整的循环节
            mat = mat * quickPower(tr, tmp);
            n = n - loopLen * tmp; // 剩下的部分暴力算
            
            for (ll i = vis[now]; i <= kcnt; i++) {
                if (n >= len[seq[i]]) { // 假设 n 还够完整的一段，直接矩阵快速幂
                    mat = mat * quickPower(tr1, len[seq[i]] - 1) * tr2;
                    n -= len[seq[i]];
                } else { // 否则暴力乘
                    mat = mat * quickPower(tr1, n);
                    printf("%lld\n", mat.o[1][1]);
                    return 0;
                }
            }
        }

    }

    return 0; 
}

1