#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int Max=100+10;
vector<int> G[Max];
int dfn[Max];
string s;
void dfs(int u,int fa){
	for(auto v:G[u]){
		if(v==fa){
			continue;
		}
		s+="(";
		dfs(v,u);
		s+=")";
	}
}
// unsigned __int128 ejc[Max<<1];
void write(unsigned __int128 x){
	if(x>=10){
		write(x/10);
	}
	putchar((char)(x%10+'0'));
}
/*
unsigned __int128 gcd(unsigned __int128 x,unsigned __int128 y){
	if(y==0){
		return x;
	}
	return gcd(y,x%y);
}
unsigned __int128 C(int n,int m){
	unsigned __int128 x=1;
	unsigned __int128 y=1;
	for(int i=1;i<=n-m;i++){
		x*=(m+i);
		y*=i;
		int tmp=gcd(x,y);
		x/=tmp;
		y/=tmp;
	}
	return x;
}
*/
unsigned __int128 f[Max][Max];
unsigned __int128 g[Max][Max];
unsigned __int128 encoder(int n, const int *p){
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			f[i][j]=0;
		}
	}
	f[n-1][n-1]=1;
	for(int i=n-1;i>=0;i--){
		for(int j=n-1;j>=0;j--){
			if(j+1<=i){
				f[i][j]+=f[i][j+1];
			}
			f[i][j]+=f[i+1][j];
		}
	}
	for(int i=1;i<=n;i++){
		G[i].clear();
	}
	for(int i=2;i<=n;i++){
		G[p[i]].push_back(i);
	}
	s="";
	dfs(1,0);
	// ejc[0]=1;
	// for(int i=1;i<=2*n;i++){
	// 	ejc[i]=ejc[i-1]*i;
	// 	write(ejc[i]);
	// 	cout<<'\n';
	// }
	unsigned __int128 ans=0;
	int nowx=0;
	int nowy=0;
	int i=1;
	for(auto c:s){
		if(nowx>nowy&&c=='('){
			nowy++;
			// unsigned __int128 tmp=C(2*(n-1)-nowx-nowy,(n-1)-nowx)-C(abs((n-1)-(nowy-1))+abs((n-1)-(nowx+1)),abs((n-1)-(nowx+1)));
			unsigned __int128 tmp=f[nowx][nowy];
			ans+=tmp;
			nowy--;
		}
		if(c=='('){
			nowx++;
		} else {
			nowy++;
		}
		i++;
		// cout<<nowx<<' '<<nowy<<' ';
		// write(ans);
		// cout<<'\n';
	}
	return ans;
}

// unsigned __int128 djc[Max*10];
// unsigned __int128 dC(int n,int m){
// 	return djc[n]/djc[m]/djc[n-m];
// }
void decoder(int n, unsigned __int128 M, int *p){
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			g[i][j]=0;
		}
	}
	g[n-1][n-1]=1;
	for(int i=n-1;i>=0;i--){
		for(int j=n-1;j>=0;j--){
			if(j+1<=i){
				g[i][j]+=g[i][j+1];
			}
			g[i][j]+=g[i+1][j];
		}
	}
	// djc[0]=1;
	// for(int i=1;i<=10*n;i++){
	// 	djc[i]=djc[i-1]*i;
	// }
	string s="";
	int nowx=0;
	int nowy=0;
	for(int i=1;i<=2*(n-1);i++){
		if(nowx>nowy){
			nowy++;
			// unsigned __int128 tmp=C(2*(n-1)-nowx-nowy,(n-1)-nowx)-C(abs((n-1)-(nowy-1))+abs((n-1)-(nowx+1)),abs((n-1)-(nowx+1)));
			unsigned __int128 tmp=g[nowx][nowy];
			if(tmp<=M){
				nowy--;
				nowx++;
				M-=tmp;
				s+="(";
			} else {
				s+=")";
			}
		} else {
			s+="(";
			nowx++;
		}
		// cout<<"!"<<nowx<<' '<<nowy<<'\n';
	}
	// cout<<"!"<<s<<'\n';
	int now=1;
	p[1]=0;
	int tot=1;
	for(auto c:s){
		if(c=='('){
			++tot;
			p[tot]=now;
			now=tot;
		} else {
			now=p[now];
		}
	}
}

/*
time:
mem:
*/