\begin{array}{c} \color{#FFFFFFff}{F}\color{#D0E4FFff}{u}\color{#A4C8FFff}{r}\color{#78ACFFff}{i}\color{#4C90FFff}{n}\color{#2064FFff}{a} \color{#0040A4ff}{F}\color{#2064FFff}{o}\color{#4C90FFff}{r}\color{#78ACFFff}{c}\color{#A4C8FFff}{a}\color{#D0E4FFff}{l}\color{#FFFFFFff}{o}\color{#D0E4FFff}{s} \end{array}

/**
 *  author:  furinaforcalos
 *  created:  10.05.2025
**/
#include <bits/stdc++.h>
#define hutao long long
using namespace std;
hutao n,m,k,dp[1000006];
hutao nhan(hutao a,hutao b)
{
    a%=m, b%=m;
    hutao q=(long double)a*b/m;
    return (a*b-q*m)%m;
}
struct heso
{
    vector<vector<hutao>> dp;
    hutao row() const {return dp.size();}
    hutao col() const {return dp[0].size();}
    auto & operator [] (hutao i) {return dp[i];}
    const auto & operator[] (hutao i) const {return dp[i]; }
    heso()=default;
    heso(hutao r, hutao c): dp(r, vector<hutao>(c)){}
    heso(const vector<vector<hutao>>&d): dp(d)
    {
        assert(d.size());
        hutao size=d[0].size();
        assert(size);
        for(auto x:d) assert(x.size()==size);
    }
    static heso identity(hutao n){
        heso a=heso(n,n);
        while(n--) a[n][n]=1;
        return a;
    }
    heso operator *(const heso &b)
    {
        heso a=*this;
        assert(a.col()==b.row());
        heso c(a.row(),b.col());
        for(hutao i=0; i<a.row(); i++)
        {
            for(hutao j=0; j<b.col(); j++)
            {
                for(hutao k=0; k<a.col(); k++)
                {
                    c[i][j]=(c[i][j]+nhan(a[i][k],b[k][j]))%m;
                }
            }
        }
        return c;
    }
    heso operator ^ (hutao exp){
        assert(row()==col());
        heso base=*this, ans=identity(row());
        for(; exp>0; exp >>= 1, base=(base*base)){
            if(exp&1) ans=(ans*base);
        }
        return ans;
    }
};
int main(){
    ios::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);
    cin>>n>>k>>m;
    heso a(1,2);
    a.dp={{(k-1)%m,1}};
    heso b(2,2);
    b.dp = {
        {(k-1)%m,1},
        {(k-1)%m,0}
    };
    b=b^(n-1);
    a=a*b;
    cout<<a.dp[0][0];
}