#include<bits/stdc++.h>
using namespace std;
typedef unsigned __int128 u128;

void write(u128 x){
    if(x>=10)write(x/10);
    cout<<(int(x%10));
}
vector<int>to[70];
void dfs(int x,vector<bool>&has){
    for(auto it:to[x]){
        has.push_back(1);
        dfs(it,has);
        has.push_back(0);
    }
}
struct Cn{
    int bj;
    u128 dp[145][145];
    void pre_set(){
        if(bj)return;
        bj=1;
        dp[0][0]=1;
        for(int i=0;i<140;i++){
            for(int j=0;j<=i;j++){
                if(j)
                    dp[i+1][j-1]+=dp[i][j];
                dp[i+1][j+1]+=dp[i][j];
            }
        }
    }   
    u128 to_u128(const vector<bool>&has){
        pre_set();
        int n=has.size();
        u128 sum=0;
        for(int i=0,cnt=0;i<n;i++){
            if(cnt&&has[i]){
                sum+=dp[n-i-1][cnt-1];
                // cerr<<'['<<n-i-1<<','<<cnt-1<<']';
            }
            if(has[i])cnt++;
            else cnt--;
        }
        return sum+1;
    } 
}en,de;
u128 encoder(int n, const int *p){
    for(int i=1;i<=n;i++)to[i].clear();
    for(int i=2;i<=n;i++)to[p[i]].push_back(i);
    vector<bool>has;
    dfs(1,has);
    // for(auto it:has)cerr<<it;cerr<<'\n';
    // cerr<<(long long)en.to_u128(has);cerr<<'\n';
    return en.to_u128(has);
}

void decoder(int n,u128 M,int *p){
    vector<bool>has;
    int N=2*n-2;
    de.pre_set();
    for(int i=0,cnt=0;i<N;i++){
        if(!cnt||de.dp[N-i-1][cnt-1]<M){
            M-=de.dp[N-i-1][cnt-1];
            has.push_back(1);
            cnt++;
        }else{
            has.push_back(0);
            cnt--;
        }
    }

    int now=1,cnt=1;
    for(auto it:has){
        // cerr<<it;
        if(it){
            p[++cnt]=now;
            now=cnt;
        }else{
            now=p[now];
        }
    }
    // cerr<<'\n';
    // cerr<<(long long)de.to_u128(has);cerr<<'\n';
}