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
#include<cstdio>
typedef long long LL;
int main()
{
    int nn,kk,pp,i,h,x,n;
    LL j[1002][12]={},d[1002][12]={};
    int bin[1001][1001]={};
    scanf("%d%d%d",&nn,&kk,&pp);
    if(kk>10)
    {
        printf("0\n");
        return 0;
    }
    for(i=0;i<11;++i)
        j[0][i]=d[0][i]=1;
    for(i=0;i<=1000;++i)
        bin[i][0]=1;
    for(i=1;i<=nn;++i)
        for(h=1;h<=i;++h)
        {
            bin[i][h]=bin[i-1][h]+bin[i-1][h-1];
            if(bin[i][h]>=pp)
                bin[i][h]-=pp;
        }
    for(x=1;x<=nn;++x)
    {
        for(n=1;n<11;++n)
        {
            for(i=0;i<x;++i)
            {
//                z[x][n]+=j[i][n]*1LL*j[x-1-i][n]%pp*bin[x-1][i]%pp;
                j[x][n]+=d[i][n-1]*j[x-1-i][n]%pp*bin[x-1][i];
                d[x][n]+=(d[i][n-1]*d[x-1-i][n]+(d[i][n]-d[i][n-1])*d[x-1-i][n-1])%pp*bin[x-1][i];
                j[x][n]%=pp;
                d[x][n]%=pp;
            }
        }
    }
    LL res=0,rb=0;
    for(i=0;i<nn;++i)
    {
        res+=j[i][kk]*j[nn-1-i][kk]%pp*bin[nn-1][i];
        res%=pp;
    }
    --kk;
    for(i=0;i<nn;++i)
    {
        rb+=j[i][kk]*1LL*j[nn-1-i][kk]%pp*bin[nn-1][i]%pp;
        if(rb>pp)
            rb-=pp;
    }
    res-=rb;
    if(res<0)
        res+=pp;
    printf("%lld\n",res);
/*    puts("z");
    for(x=0;x<6;++x)
    {
        for(n=0;n<4;++n)
            printf("%d ",z[x][n]);
        printf("\n");
    }
    puts("j");
    for(x=0;x<6;++x)
    {
        for(n=0;n<4;++n)
            printf("%d ",j[x][n]);
        printf("\n");
    }
    puts("d");
    for(x=0;x<6;++x)
    {
        for(n=0;n<4;++n)
            printf("%d ",d[x][n]);
        printf("\n");
    }
    printf("%d",z[5][3]-z[5][2]);*/
}