#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int MAXN = 150;
unsigned __int128 f[MAXN][MAXN];
// f[i][j] 表示长度为 i 的括号序列中未匹配的有括号的个数为 j 的方案数
bool is_init;
void init(){
    f[0][0] = 1;
    for(int i = 1;i<=142;i++){
        f[i][0] = f[i-1][1];
        for(int j = 1;j<=i;j++) f[i][j] = f[i-1][j-1]+f[i-1][j+1];
    }
    is_init = true;
}
void array_to_number(int n,string array,unsigned __int128 &ans){
    if(!is_init) init();
    ans = 0;
    array = "$"+array;
    int num = 0;
    for(int i = 1;i<=n;i++){
        if(array[i]=='('){
            num++;
        }else{
            // 这一个位置为 (
            ans += f[n-i][num+1];
            num--;
        }
    }
    ans++;
}
void number_to_array(int n,unsigned __int128 number,string &ans){
    if(!is_init) init();
    ans.clear();
    int num = 0;
    for(int i = 1;i<=n;i++){
        if(num+1<=(n>>1)&&f[n-i][num+1]>=number) ans.push_back('('),num++;
        else{
            ans.push_back(')');
            if(num+1<=(n>>1)) number-= f[n-i][num+1];
            num--;
        }
    }
}
vector<int> v[MAXN];
void dfs(int k,string &ans){
    ans.push_back('(');
    for(int i:v[k]){
        dfs(i,ans);
    }
    ans.push_back(')');
}
void tree_to_array(int n,const int *p,string &ans){
    for(int i = 1;i<=n;i++) v[i].clear();
    for(int i = 2;i<=n;i++){
        v[p[i]].push_back(i);
    }
    dfs(1,ans);
    ans.erase(ans.begin());
    ans.erase(--ans.end());
}
int sum;
bool flag = 0;
void dfs(int k,int fath,string &array,int *p){
    if(k==1){
        while(!array.empty()){
            sum++;
            dfs(sum,k,array,p);
        }
        return;
    }
    array.erase(array.begin());
// if(k<=10&&!flag)cout << k << " " << array << " " << *array.begin() << endl;
    flag|=k>10;
    while(*array.begin()!=')'){
        sum++;
        dfs(sum,k,array,p);
    }
    array.erase(array.begin());
    p[k] = fath;
}
void array_to_tree(int n,string array,int *p){
// cout << n << " " << array << endl;
    p[1] = 0;
    sum = 1;
    dfs(1,0,array,p);
}
unsigned __int128 encoder(int n, const int *p)
{
// cout << "I'm OK now" << flush << endl;
    string array;
// cout << "I'm OK now" << flush << endl;
    tree_to_array(n,p,array);
// cout << "I'm OK now" << flush << endl;
    unsigned __int128 ans;
// cout << array << endl;
    array_to_number(2*n-2,array,ans);
// cout << "I'm OK now" << flush << endl;
    return ans;
}
void decoder(int n, unsigned __int128 M, int *p)
{
// cout << "Receive!" << flush << endl;
    string array;
    number_to_array(2*n-2,M,array);
// cout << "OK to number_to_array!" << flush << endl;
// cout << array << flush << endl;
    array_to_tree(n,array,p);
}