CUBE-T031: Binary Lemon Tree

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int N = 1e4;
const int PM = 909091;

int dp[N + 10];

int main(){

    int x;
    scanf("%d", &x);
    dp[0] = 1;
    dp[1] = 1;
    for(int n = 2; n <= x; ++n){
        int sum = 0;
        for(int i = 0; i < n; ++i){
            sum = (sum + ((lli)dp[i] * dp[n - i - 1]) % PM) % PM;
        }
        dp[n] = sum;
    }
    cout << dp[x];

    return 0;
}