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
#include <bits/stdc++.h>
using namespace std;
#define h 10000010
long long w_gore_wyn[h], w_dol_wyn[h], w_gore[h], w_dol[h], sum_do_g[h], sum_do_d[h];
void przepisz(int m)
{
    for (int i=1;i<=m;i++)
    {
        w_dol[i]=w_dol_wyn[i];
        w_gore[i]=w_gore_wyn[i];
        w_dol_wyn[i]=0;
        w_gore_wyn[i]=0;
    }
}
int main()
{
   ios_base::sync_with_stdio(0);
   long long n, m, p; cin>>n>>m>>p; //n to sztachety
   for (int i=1;i<=m;i++)
   {
       w_gore[i]=m-i+1 ; w_dol[i]=i;
   }
   for (int i=1;i<=m;i++)
   {
     sum_do_g[i]=(sum_do_g[i-1]+w_dol[i])%p; sum_do_d[i]=(sum_do_d[i-1]+w_gore[i])%p;
    }
   for (int i=1;i<n;i++) //od 1 bo juz pierwsza przerobilismy
   {
       for (int k=1;k<=m;k++) //tutaj w dol wyn liczone jest
       {
           long long c_wczesniej=w_dol_wyn[k-1];
           long long prze_w_gore=w_gore[k];
           long long calosc=sum_do_d[m];
           long long zle1=sum_do_g[k-1]-sum_do_g[0], zle2=sum_do_d[m]-sum_do_d[k];
           w_dol_wyn[k]+=c_wczesniej;
           w_dol_wyn[k]+= ( ( prze_w_gore*(k-1) ) % p );
           w_dol_wyn[k]=w_dol_wyn[k]%p; // mod
           w_dol_wyn[k]+= ( (calosc-zle1-zle2+p)%p );
           w_dol_wyn[k]=w_dol_wyn[k]%p; //mod
       }
       for (int k=m;k>=1;k--) //tutaj w gore wyn liczone jest
       {
           long long c_wczesniej=w_gore_wyn[k+1];
           long long prze_w_dol=w_dol[k];
           long long calosc=sum_do_d[m];
           long long zle1=sum_do_g[k-1]-sum_do_g[0], zle2=sum_do_d[m]-sum_do_d[k];
           w_gore_wyn[k]+=c_wczesniej;
           w_gore_wyn[k]+= ( ( prze_w_dol*(m-k) ) % p );
           w_gore_wyn[k]=w_gore_wyn[k]%p; //mod
           w_gore_wyn[k]+= ( (calosc-zle1-zle2+p)%p );
           w_gore_wyn[k]=w_gore_wyn[k]%p; //mod
       }

       przepisz(m);
       for (int i=1;i<=m;i++)
       {
           sum_do_g[i]=(sum_do_g[i-1]+w_dol[i])%p; sum_do_d[i]=(sum_do_d[i-1]+w_gore[i])%p;
       }
   }
   long long sum=0;
   for (int i=1;i<=m;i++)
   {
       sum+=w_dol[i];
       sum%=p;
   }
   cout<<sum;



  return 0;
}