#include<bits/stdc++.h>
#define i8 unsigned __int128

const int N=140;
i8 c[N+5][N+5];
void init(){
	for(int i=0;i<=N;i++){
		c[i][0]=1;
		for(int j=1;j<=i;j++){
			c[i][j]=c[i-1][j-1]+c[i-1][j];
		}
	}
}
i8 calc(int h,int l){
	if(h<0||h>l){
		return 0;
	}
	return c[l][(l-h)/2]-c[l][(l-h)/2-1];
}

std::vector<int>e[N+5];
int a[N+5],z;
void dfs(int x){
	std::sort(e[x].begin(),e[x].end());
	for(int y:e[x]){
		a[++z]=0;
		dfs(y);
		a[++z]=1;
	}
}

i8 encoder(int n,const int *p){
	if(!c[0][0])init();
	for(int i=0;i<=n;i++){
		e[i].clear();
	}
	for(int i=1;i<=n;i++){
		e[p[i]].push_back(i);
	}
	z=0;
	dfs(1);
	int h=0,zong=n*2-2;i8 ans=0;
	for(int i=1;i<=zong;i++){
		if(a[i]==0){
			h++;
		}
		else{
			h--;
			ans+=calc(h+2,zong-i);
			//printf("add %d:%d\n",i,(int)calc(h+2,zong-i));
		}
	}
	return ans;
}

//int b[N+5];
int st[N+5];
void decoder(int n,i8 M, int *p){
	if(!c[0][0])init();
	int h=0,zong=n*2-2,top=1,cnt=1;
	p[1]=0;
	st[1]=1;
	for(int i=1;i<=zong;i++){
		i8 x=calc(h+1,zong-i);
		if(M>=x){
			M-=x;
			top--;
			h--;
			//printf("down %d\n",i);
			//b[i]=0;
		}
		else{
			h++;
			//b[i]=1;
			//printf("up %d\n",i);
			st[++top]=++cnt;
			p[cnt]=st[top-1];
		}
	}
}
/*
int x[10]={0,0,4,1,1,3},y[10];
int main(){
	int n=5;i8 oo=0;
	decoder(n,oo=encoder(n,x),y);
	for(int i=1;i<=n;i++){
		printf("%d ",y[i]);
	}
	printf(":%d\n",(int)oo);
}
*/