答案是2^n / (n + 1)!。概率可以通过合法方案数/总方案数来计算。合法方案数f(n)=Σf(i) * f(n-i-1), 即为卡特兰数，故f(n)=C(2n, n) / (n + 1)。总方案数为C(2n, 2) * C(2n – 2, 2) … C(2, 2) / n! = (2n)! / n! / 2^n。两者相除即为答案。除法取模的话用逆元来计算。总复杂度O(n)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7; 
int n;
ll ans = 1;
ll powMod(ll a, ll k) { ll ret = 1; while(k) { if(k & 1) ret = ret * a % mod; a = a * a % mod; k >>= 1;} return ret;}
ll inv(ll a) { return powMod(a, mod - 2);}
int main()
{
    cin >> n;
    for(int i = 1; i <= n + 1; ++i) ans = ans * i % mod;
    ans = powMod(2, n) * inv(ans) % mod;
    cout << ans << endl;
    return 0;
}