#include <bits/stdc++.h>
#define il inline
using namespace std;
typedef long long ll;
ll mod;
il ll qp(ll a,ll b){
    ll ans=1ll;
    while(b){
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod,b>>=1;
    }return ans;
}
il ll v(ll a,ll b){return (a*qp(b,mod-2ll))%mod;}
const int N=3005;
ll f1[N]={0,1,4,6,12,19,35,58,102,172,296,501,853,1442};
ll f2[N]={0,1,9,17,47,94,227,477,1073,2290,4985,10637,22779};
ll f3[N]={0,1,16,36,120,281,803,1960};
ll f4[N]={0,1,25,65,245,649,2089,5705};
ll f5[N]={0,1,36,106,436,1281,4511,13506};
ll f6[N]={0,1,49,0,0,2274,8595,27853};
ll f7[N]={0,0,0,0,0,0,14967,52032};
ll f8[N]={0,0,0,0,0,0,0,90225};
int n,m,k;ll f[N],p[N],a[N];
ll x,y,z;
int main(){
    //freopen("c_1.in","r",stdin);
    scanf("%d%d%lld",&n,&m,&mod);

    p[0]=1ll;for(int i=1;i<=7;++i) p[i]=(p[i-1]*1ll*m)%mod;

    f[1]=1ll;
    f[2]=(m+1ll)*(m+1ll)%mod;
    f[3]=v(1,3)*p[3]+2ll*p[2]+v(8,3)*p[1]+1ll;
    f[4]=v(7,3)*p[3]+5ll*p[2]+v(11,3)*p[1]+1ll;
    f[5]=v(7,12)*p[4]+v(17,3)*p[3]+v(89,12)*p[2]+v(13,3)*p[1]+1ll;
    f[6]=v(25,6)*p[4]+v(38,3)*p[3]+v(71,6)*p[2]+v(16,3)*p[1]+1ll;
    f[7]=v(5,6)*p[5]+v(37,3)*p[4]+v(133,6)*p[3]+v(47,3)*p[2]+6*p[1]+1ll;

    for(int i=1;i<=7;++i) f[i]%=mod;

    a[1]=2ll,a[2]=2ll*m,a[3]=-2ll*(m+1ll),a[4]=(2ll-f[2]),a[5]=2ll*m,a[6]=m*m;
    for(int i=1;i<=6;++i) a[i]=(a[i]%mod+mod)%mod;

    for(int i=8;i<=n;++i)
        for(int j=1;j<=6;++j) f[i]=(f[i]+f[i-j]*a[j])%mod;

    printf("%lld",f[n]);
    return 0;
}
/*
1,4,6,12,19,35,58,102,296,501
2,2,3,3,4,4,5,5,6,6
0,2,3,9,15,31,53,97,290,495

1,4,6,12,19,35,58,102,172,296,501,853,1442
1,9,17,47,94,227,477,1073,2290,4985,10637,22779

g(1,x)=1
g(2,x)=x^2+2x+1

2,2,−4,−2,2,1)
m=2m=2m=2：(2,4,−6,−7,4,4)(2,4,-6,-7,4,4)(2,4,−6,−7,4,4)
m=3m=3m=3：(2,6,−8,−14,6,9)(2,6,-8,-14,6,9)(2,6,−8,−14,6,9)
*/