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
#include <bits/stdc++.h>                                                        
using namespace std;                                                            
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)            
using ll =  long long;                                                          
using vll = vector<ll>;                                                         
                                                                                
int n, m;                                                                       
ll p;                                                                           
                                                                                
#define ra(x) ((x) >= p ? (x)-p : x)                                            
#define rs(x) ((x) < 0 ? (x)+p : x)                                             
#define rm(x) ((x) % p)                                                         
                                                                                
int main()                                                                  
{                                                                               
    fastIO;                                                                     
    cin >> n >> m >> p;     

    if (m == 1)
    {
    	cout << 1;
    	return 0;
    }                                                  
                                                                                
    vll old(m), oldPref(m), oldPrefPref(m);                                     
    vll nww(m), nwwPref(m), nwwPrefPref(m);                                     
                                                                                
    nww[0] = nwwPref[0] = nwwPrefPref[0] = 1;                                   
    for (int i = 1; i < m; ++i)                                                 
    {                                                                           
        nww[i] = i + 1;                                                         
        nwwPref[i] = ra(nwwPref[i-1] + i + 1);                                  
        nwwPrefPref[i] = ra(nwwPrefPref[i-1] + nwwPref[i]);                     
    }                                                                           
                                                                                
    //cout << nww << nwwPref << nwwPrefPref << '\n';                            
                                                                                
    while(--n)                                                                  
    {                                                                           
        swap(nww, old);                                                         
        swap(nwwPref, oldPref);                                                 
        swap(nwwPrefPref, oldPrefPref);                                         
                                                                                
        nww[0] = old[m-1];                                                      
        for (int i = 1; i < m - 1; ++i)                                         
            nww[i] = rs(rm((i+1)*rs(oldPref[m-1]-oldPref[m-2-i])) - oldPrefPref[i-1]);                                                                          
        nww[m-1] = rs(rm(m*(oldPref[m-1])) - oldPrefPref[m-2]);                 
                                                                                
        nwwPref[0] = nwwPrefPref[0] = nww[0];                                   
        for (int i = 1; i < m; ++i)                                             
        {                                                                       
            nwwPref[i] = ra(nwwPref[i-1] + nww[i]);                             
            nwwPrefPref[i] = ra(nwwPrefPref[i-1] + nwwPref[i]);                 
        }                                                                       
        //cout << nww << nwwPref << nwwPrefPref << '\n';                        
    }                                                                           
                                                                                
    cout << nwwPref.back();                                                     
                                                                                                                                                       
    return 0;                                                                   
}