C++ :

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>

typedef long long int64;

const int maxK = 1000010;

struct Matrix
{
    int ele[3][3]; static int Mod;
    Matrix() {memset(ele, 0, sizeof ele);} 
    Matrix(const Matrix& b) {*this = b;} 
    Matrix& operator=(const Matrix& b)
    {memcpy(ele, b.ele, sizeof ele); return *this;}
   
    int* const operator[](const int& Ind) {return ele[Ind];} 
    const int* const operator[](const int& Ind) const {return ele[Ind];} 
    Matrix& operator*=(const Matrix& b)
    {
        static Matrix res;
        for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
        {
            int64 tmp = 0;
            for (int k = 0; k < 3; ++k)
                tmp += (int64)ele[i][k] * b[k][j];
            res[i][j] = tmp % Mod;
        } 
        return *this = res;
    } 
} matr[maxK], A, B, C;

int Fib[maxK << 3], Ind_Fib[maxK], Ind_Cyc[maxK], len[maxK], p, K, Matrix::Mod = 0;
int64 n;

Matrix pow(const Matrix& a, int64 n)
{
    Matrix res, tmp(a);
    res[0][0] = res[1][1] = res[2][2] = 1;
    for (; n; n >>= 1, tmp *= tmp) if (n & 1) res *= tmp;
    return res;
} 

int pow(int a, int64 n, int Mod)
{
    int64 res = 1, tmp = a;
    for (; n; n >>= 1, (tmp *= tmp) %= Mod) if (n & 1) (res *= tmp) %= Mod;
    return res;
} 

int gcd(int n, int m)
{
    for (int r; m; n = m, m = r) r = n % m;
    return n;
}

int main()
{
    scanf("%lld%d%d", &n, &K, &p);
    Matrix::Mod = p;
    Fib[1] = Fib[2] = 1;
    for (int i = 3; ; ++i)
    {
        Fib[i] = (Fib[i - 1] + Fib[i - 2]) % K;
        if (!Ind_Fib[Fib[i]]) Ind_Fib[Fib[i]] = i;
        if (Fib[i] == 1 && Fib[i - 1] == 1) break;
    } 

    int tmp = K, mul_Inv = 1;
    for (int i = 2; i * i <= tmp; ++i)
    if (tmp % i == 0)
    {
        mul_Inv *= i - 1;
        while ((tmp /= i) % i == 0) mul_Inv *= i;
    } 
    if (tmp > 1) mul_Inv *= tmp - 1;

    A[0][1] = A[1][0] = A[1][1] = A[2][2] = 1;
    B[0][0] = B[1][1] = B[2][2] = 1;
    C[0][0] = C[1][1] = C[2][2] = 1;

    memset(Ind_Cyc, 0xff, sizeof Ind_Cyc);
    int tot = 0, ths = 1, ans = 0; int64 totlen = 0;
    for (; Ind_Cyc[ths] == -1; ++tot)
    {
        if (gcd(ths, K) > 1 || !Ind_Fib[pow(ths, mul_Inv - 1, K)])
        {
            for (int i = 0; i < tot; ++i) B *= matr[i];
            B *= pow(A, n - totlen);
            ans = ((B[1][0] - B[2][0]) % p + p) % p;
            printf("%d\n", ans);
            return 0;
        } 

        Ind_Cyc[ths] = tot;
        int nxt = pow(ths, mul_Inv - 1, K);
        len[tot] = Ind_Fib[nxt];

        if (n < totlen + len[tot])
        {
            for (int i = 0; i < tot; ++i) B *= matr[i];
            B *= pow(A, n - totlen);
            ans = ((B[1][0] - B[2][0]) % p + p) % p;
            printf("%d\n", ans);
            return 0;
        }
        
        totlen += len[tot];
        matr[tot] = pow(A, len[tot]);
        ++matr[tot][2][0] %= p;
        ++matr[tot][2][1] %= p;
        ths = ((int64)ths * Fib[len[tot] - 1]) % K;
    } 

    int start = Ind_Cyc[ths];
    for (int i = 0; i < start; ++i) B *= matr[i], n -= len[i];
    totlen = 0;
    for (int i = start; i < tot; ++i) C *= matr[i], totlen += len[i];

    B *= pow(C, n / totlen);
    n %= totlen, totlen = 0;
    for (int i = start; i < tot; ++i)
    {
        if (n < totlen + len[i])
        {
            B *= pow(A, n - totlen);
            ans = ((B[1][0] - B[2][0]) % p + p) % p;
            printf("%d\n", ans);
            return 0;
        } 
        B *= matr[i];
        totlen += len[i];
    } 
    return 0;
} 

Pascal :

const
    maxk=1001000;
type
    matrix=array[1..3,1..3]of int64;
var
    a:array[0..maxk*6]of longint;
    first,last,b,len:array[0..maxk]of longint;
    pre:array[0..maxk]of longint;
    n,k,p,x,y:int64;
    ans,aa,bb:matrix;

procedure exgcd(a,b:int64);
var
    t:int64;
begin
    if b=0 then
    begin
        if a=1 then x:=1
        else x:=0;
        y:=0;
        exit;
    end;
    exgcd(b,a mod b);
    t:=x;
    x:=y;
    y:=t-(a div b)*y;
end;

procedure work;
var
    i:longint;
begin
    a[1]:=1;a[2]:=1;i:=2;
    while true do
        begin
            inc(i);
            a[i]:=(a[i-1]+a[i-2])mod k;
            if first[a[i]]=0 then first[a[i]]:=i;
            if (a[i]=1) and (a[i-1]=1) then break;
        end;
    for i:=1 to k-1 do
        begin
            exgcd(i,k);
            pre[i]:=(x mod k+k)mod k;
        end;
    b[1]:=1;last[1]:=1;i:=1;
    while true do
        begin
            len[i]:=first[pre[b[i]]]-1;
            if len[i]<0 then break;
            inc(i);
            b[i]:=int64(a[len[i-1]])*b[i-1]mod k;
            if last[b[i]]>0 then break;
            last[b[i]]:=i;
        end;
    aa[1,2]:=1;aa[2,1]:=1;aa[2,2]:=1;aa[3,3]:=1;
    bb:=aa;bb[3,2]:=p-1;
end;

operator *(a,b:matrix)c:matrix;
var
    i,j,k:longint;
begin
    fillchar(c,sizeof(c),0);
    for i:=1 to 3 do
        for j:=1 to 3 do
            for k:=1 to 3 do
                c[i,k]:=(c[i,k]+a[i,j]*b[j,k])mod p;
end;

function f(a:matrix;n:int64):matrix;
begin
    fillchar(f,sizeof(f),0);
    f[1,1]:=1;f[2,2]:=1;f[3,3]:=1;
    while n>0 do
        begin
            if n and 1=1 then f:=f*a;
            a:=a*a;
            n:=n>>1;
        end;
end;

procedure main;
var
    i,j:longint;
    s:matrix;
    sum:int64;
begin
    read(n,k,p);
    if n<3 then
    begin
        writeln(1);
        exit;
    end;
    work;
    ans[1,1]:=1;ans[2,2]:=1;ans[3,3]:=1;
    if n>len[1] then
        begin
            dec(n,len[1]+1);
            ans:=ans*f(aa,len[1]-2)*bb;
        end
    else
        begin
            ans:=ans*f(aa,n-2);
            n:=0;
        end;
    i:=2;
    while n>0 do
        begin
            if pre[b[i]]=0 then
            begin
                ans:=ans*f(aa,n);
                n:=0;
                break;
            end;
            if len[i]<0 then
            begin
                ans:=ans*f(aa,n);
                n:=0;
                break;
            end;
            if last[b[i]]<i then break;
            if n>len[i] then
                begin
                    dec(n,len[i]+1);
                    ans:=ans*f(aa,len[i])*bb;
                end
            else
                begin
                    ans:=ans*f(aa,n);
                    n:=0;
                end;
            inc(i);
        end;
    if n=0 then
    begin
        writeln((ans[1,2]+ans[2,2]+ans[3,2])mod p);
        exit;
    end;
    j:=i;
    sum:=0;
    fillchar(s,sizeof(s),0);
    s[1,1]:=1;s[2,2]:=1;s[3,3]:=1;
    for i:=last[b[j]] to j-1 do
        begin
            inc(sum,len[i]+1);
            s:=s*f(aa,len[i])*bb;
        end;
    ans:=ans*f(s,n div sum);
    n:=n mod sum;
    i:=last[b[j]];
    while n>0 do
        begin
            if n>len[i] then
                begin
                    ans:=ans*f(aa,len[i])*bb;
                    dec(n,len[i]+1);
                end
            else
                begin
                    ans:=ans*f(aa,n);
                    n:=0;
                end;
            inc(i);
        end;
    writeln((ans[1,2]+ans[2,2]+ans[3,2])mod p);
end;

begin
    main;
end.