#include<bits/stdc++.h>
typedef unsigned __int128 ull;
using namespace std;
const int N=200;

int top=0;
char s[N];
ull f[N][N];
bool flag;

void init(int n=150){
    if(flag)return;
    flag=1;
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        f[i][0]=f[i-1][1];
        for(int j=1;j<=n;j++)f[i][j]=f[i-1][j-1]+f[i-1][j+1];
    }
}

void dfs(int x,int n,const int *p){
    for(int i=1;i<=n;i++){
        if(p[i]!=x)continue;
        s[++top]='(';
        dfs(i,n,p);
        s[++top]=')';
    }
}

ull encoder(int n,const int *p){
    init();
    top=0;
    dfs(1,n,p);
    int id=0;
    ull ret=1;
    for(int i=1;i<=top;i++){
        if(s[i]==')')ret+=f[top-i][id+1],id--;
        else id++;
    }
    return ret;
}

void decoder(int n,ull M,int *p){
    init();
    int id=0,len=2*n-2;
    for(int i=1;i<=len;i++){
        if(id+1<=(len>>1)&&f[len-i][id+1]>=M)s[i]='(',id++;
        else{
            s[i]=')';
            if(id+1<=(len>>1))M-=f[len-i][id+1];
            id--;
        }
    }
    int cnt=1,now=1;
    for(int i=1;i<=len;i++){
        if(s[i]=='(')p[++cnt]=now,now=cnt;
        else now=p[now];
    }
}