Language: C++

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define MAX ((int)1e9 + 5)
#define MAXL ((ll)1e15 + 5)
#define MAX_X ((int)1e5 + 2)
#define pi (2.0*acos(0))
#define M ((int)1e6 + 7)
//#define MOD ((int)998244353 + 0)
#define NN ((int)1e5 + 7)
#define N ((int)5e3 + 7)
#define eps (0)
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
#define logn 29
#define endl "\n"
#define mp make_pair
//#define int ll


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;

/*fast io
ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/




typedef tree < pair < int, pair < int, int > >,  null_type,  less < pair < int, pair < int, int > > >,  rb_tree_tag,  tree_order_statistics_node_update > o_set;
/// o_set s;
/// s.order_of_key(k) : Number of items strictly smaller than k .
/// *(s.find_by_order(k)) : K-th element in a set (counting from zero).

int MOD;

bool flag;

map < int , int > dpp[N/2][N] , cum[N/2][N], pro[N/2][N];
map < int , bool > vdpp[N/2][N] , vcum[N/2][N], vpro[N/2][N];

int call(int pos , int last , int sum);

int call_cum(int pos , int upp , int sum)
{
    if(upp<0 || sum<0) return 0;

    if(vcum[pos][upp][sum]) return cum[pos][upp][sum];
    vcum[pos][upp][sum] = 1;
    int ans = call(pos - 1, upp , sum - upp) + call_cum(pos , upp-1, sum);
    if(ans>=MOD) ans -= MOD;
    return cum[pos][upp][sum] = ans;
}

int call_pro(int pos , int upp , int sum)
{
    if(upp<0 || sum<0) return 0;

    if(vpro[pos][upp][sum]) return pro[pos][upp][sum];
    vpro[pos][upp][sum] = 1;
    int ans = ((ll)upp*call(pos - 1, upp , sum - upp)%MOD) + call_pro(pos , upp-1, sum);
    if(ans>=MOD) ans -= MOD;
    return pro[pos][upp][sum] = ans;
}

int call(int pos , int last , int sum)
{
    if(sum<0 || last<0) return 0;
    if(pos==0){
        if(flag) return last+1;
        return 1;
    }

    if(vdpp[pos][last][sum]) return dpp[pos][last][sum];
    vdpp[pos][last][sum] = 1;

    int upp = min ( last , sum );

    int ans = (ll)(last+1)*call_cum( pos , upp , sum )%MOD;
    ans -= call_pro( pos , upp , sum );
    if(ans<0) ans += MOD;

    return dpp[pos][last][sum] = ans;

}

int main()
{
    fastio;
    int n , ans = 0;
    cin>>n>>MOD;
    if(n==2){
        ans = n*(n+1)/2;
        cout<<ans<<endl;
        return 0;
    }
    flag = !(n&1);
    for(int i = 1; i<=n; i++){
        for(int j = 0; j<n-1; j++){
            int ele = i+j;
            int gap = n - ele;
            if(gap<0 || j>gap) continue;
            gap = gap - j + 1;
            ans += (ll)gap*call( (n-3)/2 , j , i - 1)%MOD;
            if(ans >= MOD) ans -= MOD;
        }
    }
    cout<<ans<<endl;
    return 0;
}

// 3 998244353
// 6 966666661
// 96 925309799


Compiler output:
/tmp/cclayjUO.o: in function `call_cum(int, int, int)':
a.cc:(.text+0x4f): relocation truncated to fit: R_X86_64_PC32 against symbol `vcum' defined in .bss section in /tmp/cclayjUO.o
a.cc:(.text+0xd5): relocation truncated to fit: R_X86_64_PC32 against symbol `vcum' defined in .bss section in /tmp/cclayjUO.o
/tmp/cclayjUO.o: in function `call_pro(int, int, int)':
a.cc:(.text+0x1d0): relocation truncated to fit: R_X86_64_PC32 against symbol `vpro' defined in .bss section in /tmp/cclayjUO.o
a.cc:(.text+0x256): relocation truncated to fit: R_X86_64_PC32 against symbol `vpro' defined in .bss section in /tmp/cclayjUO.o
/tmp/cclayjUO.o: in function `__tcf_4':
a.cc:(.text+0x7ae): relocation truncated to fit: R_X86_64_PC32 against symbol `vcum' defined in .bss section in /tmp/cclayjUO.o
a.cc:(.text+0x7bc): relocation truncated to fit: R_X86_64_PC32 against symbol `vcum' defined in .bss section in /tmp/cclayjUO.o
/tmp/cclayjUO.o: in function `__tcf_5':
a.cc:(.text+0x7e9): relocation truncated to fit: R_X86_64_PC32 against symbol `vpro' defined in .bss section in /tmp/cclayjUO.o
a.cc:(.text+0x7f7): relocation truncated to fit: R_X86_64_PC32 against symbol `vpro' defined in .bss section in /tmp/cclayjUO.o
/tmp/cclayjUO.o: in function `__static_initialization_and_destruction_0()':
a.cc:(.text+0x99e): relocation truncated to fit: R_X86_64_PC32 against symbol `vcum' defined in .bss section in /tmp/cclayjUO.o
a.cc:(.text+0x9fd): relocation truncated to fit: R_X86_64_PC32 against symbol `vpro' defined in .bss section in /tmp/cclayjUO.o
collect2: error: ld returned 1 exit status