정상 회담 2(BOJ 1670)

1670.cpp

#include<iostream>
using namespace std;
long long dp[5002];
const long long MOD = 987654321;
int main()
{
	int n;
	cin>>n;
	n/=2;
	dp[0]=dp[1]=1;
	
	for(int i=2;i<=n;i++)
	{
		dp[i]=0;
		for(int j=0;j<i;j++)
			dp[i]+=((dp[j]%MOD)*(dp[i-j-1]%MOD)) % MOD;
	}
	cout<<dp[n]%MOD;
}