题目描述 求长度为 � n（ � ≥ 2 n≥2且 � n是偶数）的，由"()[]{}"六种字符组成，并且合法的括号匹配序列数量。答案对 1 0 9 + 7 10 9 +7取模。 合法规则：

空串是合法的。

如果P是合法的，那么(P)，[P]，{P}也是合法的。

如果P，Q是合法的，那么PQ也是合法的。 输入描述 一行一个整数n，表示字符串的长度

输出描述 输出合法的括号匹配序列数量对 1 0 9 + 7 10 9

+7取模的值。

#include<bits/stdc++.h>
using namespace std;
int ans = 0, n;
void dfs (int l, int r, string str){
    if(str.lenght() == 2 * n){
        ans++;
        return;
    }
    if(l < n){
        str.push_back('[');
        dfs(l + 1, r, str);
        str.pop_back();
    }
    if(r < l){
        str.push_back('{');
        dfs(l, r + 1, str);
        str.pop_back();
    }
}
int main(){
    while(cin >> n){
        ans = 0;dfs(0, 0, "");
        cout << ans << endl;
    }
    return 0;
}