CSES - Shared codeLink to this code:
https://cses.fi/paste/ce5e43773881dfff3d2665/
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int MOD2 = 2*(1e9+7);
int main()
{
FASTIO
int n;
cin >> n;
int sum = (n*(n+1))/2;
vector<unsigned> dp(sum+1,0); // UINT_MAX > 2*MOD2
dp[0] = 1;
if(sum&1)
{
cout << 0 << endl;
return EXIT_SUCCESS;
}
sum /= 2;
for(int i=1; i<=n; i++)
{
for(int j=sum; j>=0; j--)
{
if(i+j <= sum)
{
dp[i+j] += dp[j];
dp[i+j] %= MOD2;
}
}
}
cout << dp[sum]/2 << endl;
return EXIT_SUCCESS;
}