给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，则它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有 卡特兰数 - 图1 个（出栈匹配 / 括号匹配合法方案都属于卡特兰数）

    1. int qpow(int a, int b, int p) {
    2.     int res = 1;
    3.     while (b) {
    4.         if (b & 1)
    5.             res = res*a%p;
    6.         a = a*a%p;
    7.         b >>= 1;
    8.     }
    9.     return res;
    10. }
    12. signed main() {
    13.     int n;
    14.     cin >> n;
    15.     int a = n*2, b = n;
    16.     int ans = 1;
    17.     for (int i = a; i > a-b; i--) 
    18.         ans = ans*i%MOD;
    19.     for (int i = 1; i <= b; i++) 
    20.         ans = ans*qpow(i, MOD-2, MOD)%MOD;
    21.     ans = ans*qpow(n+1, MOD-2, MOD)%MOD;
    22.     cout << ans << "\n";
    23.     return 0;
    24. }