1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
long long n,m;
vector <vector <long long> > je;
bool czyzaw(pair<int,int> a, pair<int,int> b){
    if (max(a.first,b.first)<min(a.second,b.second)){
        return 1;
    }
    return 0;
}
vector <vector <long long> > mnoz(vector <vector <long long> > &a,vector <vector <long long> > &b,long long c){
    long long k=a.size();
    vector <vector <long long > > wynik;
    vector <long long> tmp;
    tmp.resize(k,0);
    wynik.resize(k,tmp);
        for (int i=0; i<k;i++){
            for (int j=0; j<k;j++){
                for (int i2=0; i2<k;i2++){
                    wynik[i][j]+=a[i][i2]*b[i2][j];
                    wynik[i][j]%=c;
                }
            }
        }
    return wynik;
}
vector <vector <long long > > potenga (vector<vector<long long> > & a,int b,long long c){
    if (b==0){
        return je;
    }
   if (b%2==1){
        vector <vector <long long> > tmp=potenga(a,b-1,c);
        return mnoz(a,tmp,c);
   }else{
       vector <vector <long long> > tmp=potenga(a,b/2,c);
       return mnoz(tmp,tmp,c);
   }
}
/*void rekur(int x,vector <pair<int,int> > & vv){
if (x==n){
    bool czek=1;
    for (int j=0; j+1<vv.size();j++){
        czek*=czyzaw(vv[j],vv[j+1]);
    }
    wynik+=czek;
    return;
}
    //cout << x<<"\n";
    for (int i=0; i<m;i++){
        for (int j=i+1; j<=m;j++){
            vv.push_back(make_pair(i,j));
            rekur(x+1,vv);
            vv.pop_back();
        }
    }
}*/
int main(){
    long long p;
    cin >> n >> m>>p;
    if (n!=1){
        vector <pair<int,int> > cos;
        vector <vector <long long> > d;
        d.resize(m*m);
        je.resize(m*m);
        for (int i=0; i<m;i++){
            for (int j=i+1; j<=m;j++){
                cos.push_back(make_pair(i,j));
            }
        }
        for (int i=0; i<m*m;i++){
            d[i].resize(m*m,0);
            je[i].resize(m*m,0);
            je[i][i]=1;

        }
        //cout << "test5"<<endl;
        for (int i=0; i<cos.size();i++){
            for (int j=0; j<cos.size();j++){
                d[i][j]=czyzaw(cos[i],cos[j]);
            }
        }
        d=potenga(d,n-1,p);
        long long wynik=0;
        for (int i=0;i<m*m;i++){
            for (int j=0; j<m*m;j++){
                wynik+=d[i][j]%p;
                wynik%=p;
            }
        }
        cout << wynik<<endl;
    }else{
        cout << (m*(m+1)/2)%p<<endl;
    }
}