Binary lemon tree

#include<stdio.h>
typedef long long int ll;
ll const mod = 909091;

ll dp[10010];

ll cal(int n){
    if(n <= 1)return 1;
    if(dp[n] != -1)return dp[n] % mod;
    ll ans = 0;
    for(int i = 0 ; i < n ; i ++){
        ans += ((cal(i) % mod) *(cal(n-i-1) % mod)) % mod;
    }
    return dp[n] = ans % mod;
}

int main()
{
    for(int i = 0 ; i < 10010 ; i ++){
        dp[i] = -1;
    }
    int n;
    scanf("%d",&n);
    printf("%lld",cal(n));
    return 0;
}