#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define UI7 unsigned __int128
const int N=70;
const int INF=2e9;
int siz[N+5],son[N+5][2];
UI7 f[N+5];
vector<int> v[N+5];
void print128(UI7 m){
    if(m>=10) print128(m/10);
    printf("%d",(int)(m%10));
}
void en_dfs(int rt){
    if(v[rt].size()==0) return;
    son[rt][0]=v[rt][0];
    en_dfs(v[rt][0]);
    for(int j=1;j<(int)v[rt].size();j++){
        son[v[rt][j-1]][1]=v[rt][j];
        en_dfs(v[rt][j]);
    }
}
UI7 getmap(int rt){
    if(rt==0) return 1;
    UI7 rtn=getmap(son[rt][1]);
    rtn=(getmap(son[rt][0])-1)*f[siz[son[rt][1]]]+rtn;
    siz[rt]=siz[son[rt][0]]+siz[son[rt][1]]+1;
    for(int j=0;j<siz[son[rt][0]];j++){
        rtn+=f[j]*f[siz[rt]-j-1];
    }
    return rtn;
}
void en_Init(int n){
    for(int i=0;i<=n;i++){
        v[i].clear();
        siz[i]=0;
        son[i][0]=son[i][1]=0;
    }
}
unsigned __int128 encoder(int n, const int *p){
    if(f[0]==0){
        f[0]=1;
        for(int i=1;i<N;i++){
            for(int j=0;j<i;j++){
                f[i]+=f[j]*f[i-j-1];
            }
        }
    }
    for(int i=1;i<=n;i++){
        v[p[i]].push_back(i);
    }
    en_dfs(v[0][0]);
    UI7 rtn=getmap(son[v[0][0]][0]);
    en_Init(n);
    return rtn;
}
int cnt,root;
void solvemap(int& rt,int all,UI7 t){
    rt=++cnt;
    // printf("svm(rt:%d all:%d t:",rt,all);print128(t);printf(")\n");
    for(int j=0;j<all;j++){
        // printf("j:%d ",j);print128(f[j]*f[all-j-1]);printf("\n");
        if(f[j]*f[all-j-1]<t) t-=f[j]*f[all-j-1];
        else{
            // printf("svm:rt:%d all:%d j:%d\n",rt,all,j);
            if(j!=0) solvemap(son[rt][0],j,(t-1)/f[all-j-1]+1);
            if(all-j-1!=0) solvemap(son[rt][1],all-j-1,(t-1)%f[all-j-1]+1);
            // printf("svm:rt:%d all:%d j:%d son{%d %d}\n",rt,all,j,son[rt][0],son[rt][1]);
            return;
        }
    }
}
void de_dfs(int rt,int *p){
    if(son[rt][0]){
        p[son[rt][0]]=rt;
        de_dfs(son[rt][0],p);
    }
    if(son[rt][1]){
        p[son[rt][1]]=p[rt];
        de_dfs(son[rt][1],p);
    }
}
void de_Init(int n){
    for(int i=1;i<=n;i++){
        son[i][0]=son[i][1]=0;
    }
    root=0;
    cnt=0;
}
void decoder(int n, unsigned __int128 M, int *p){
    if(f[0]==0){
        f[0]=1;
        for(int i=1;i<N;i++){
            for(int j=0;j<i;j++){
                f[i]+=f[j]*f[i-j-1];
            }
        }
    }
    // printf("M:");print128(M);printf("\n");
    root=++cnt;
    solvemap(son[root][0],n-1,M);
    de_dfs(root,p);
    de_Init(n);
    // for(int i=1;i<=n;i++){
    //     printf("p[%d]:%d\n",i,p[i]);
    // }
}
/*
5
4
0 1 2 3
7
0 1 1 2 2 3 3
5
0 1 1 1 1
5
0 1 1 1 3
12
0 1 1 1 2 2 4 7 6 6 6 6
*/
/*
1
70
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
*/