CUBE-031: ต้นมะนาวทวิภาค (Binary lemon tree)

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const lli N = 909091;

int main(){

    int n;
    scanf("%d", &n);

    lli dp[n+1];
    dp[0] = 1;
    dp[1] = 1;
    for(int i=2;i<=n;i++){
        dp[i] = 0;
        for(int j=1;j<=i;j++){
            dp[i] += dp[j-1] * dp[i-j];
            dp[i] %= N;
        }
    }
    printf("%lld", dp[n]);

    return 0;
}