#include<bits/stdc++.h>
using namespace std;
namespace SOLUTION{
    const int maxn=72;
    typedef unsigned __int128 exll;
    bool is_init=false;
    exll f[maxn][maxn];
    inline void init(){
        for(int j=0;j<=70;++j){
            f[0][j]=1;
        }
        for(int i=1;i<=70;++i){
            for(int j=i+1;j<=70;++j){
                f[i][j]=f[i-1][j]+f[i][j-1];
            }
        }
    }
    bool vec[maxn<<1];
    vector<int>e[maxn];
    inline void dfs(int u,int &tot){
        vec[++tot]=true;
        for(int v:e[u]){
            dfs(v,tot);
        }
        vec[++tot]=false;
    }
    inline exll Encoder(int n,const int *p){
        if(!is_init){
            init();
            is_init=true;
        }
        for(int i=2;i<=n;++i){
            e[p[i]].push_back(i);
        }
        int tot=0;
        dfs(1,tot);
        for(int i=1;i<n;++i){
            e[i].clear();
        }
        /*cout<<"encode: tot: "<<tot<<"\n";
        for(int i=1;i<=tot;++i){
            cout<<vec[i]<<" ";
        }
        cout<<"\n";*/
        exll res=0;
        int inleave=n,outleave=n;
        for(int i=1;i<=(n<<1);++i){
            if(vec[i]){
                res+=f[inleave][outleave-1];
                --inleave;
            }
            else{
                --outleave;
            }
        }
        //cout<<"result: "<<(int)res<<"\n";
        return res;
    }
    int sta[maxn];
    inline void Decoder(int n,exll code,int *p){
        if(!is_init){
            init();
            is_init=true;
        }
        int inleave=n,outleave=n;
        for(int i=1;i<=(n<<1);++i){
            if(code>=f[inleave][outleave-1]){
                code-=f[inleave][outleave-1];
                --inleave;
                vec[i]=true;
            }
            else{
                --outleave;
                vec[i]=false;
            }
            //cout<<"after "<<i<<"-th optimize, code: "<<(int)code<<"\n";
        }
        /*cout<<"decode:\n";
        for(int i=1;i<=(n<<1);++i){
            cout<<vec[i]<<" ";
        }
        cout<<"\n";*/
        int top=0,tot=0;
        sta[0]=0;
        for(int i=1;i<=(n<<1);++i){
            if(vec[i]){
                p[++tot]=sta[top];
                sta[++top]=tot;
            }
            else{
                --top;
            }
        }
    }
    //this function is to debug.
    /*inline int Main(){
        int test;
        cin>>test;
        while(test--){
            int n;
            cin>>n;
            int *p=new int[n+1];
            for(int i=1;i<=n;++i){
                cin>>p[i];
            }
            exll code=Encoder(n,p);
            for(int i=1;i<=n;++i){
                p[i]=0;
            }
            Decoder(n,code,p);
            for(int i=1;i<=n;++i){
                cout<<p[i]<<" ";
            }
            cout<<"\n";
            delete[] p;
        }
        return 0;
    }*/
}
/*int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    SOLUTION::Main();
    return 0;
}*/
unsigned __int128 encoder(int n,const int *p){
    return SOLUTION::Encoder(n,p);
}
void decoder(int n,unsigned __int128 M,int *p){
    SOLUTION::Decoder(n,M,p);
}
/*
1
3 
0 1 2
1 1 0 1 0
5
5
0 1 1 1 1
5
0 1 2 3 4
5
0 1 1 2 2
5
0 1 2 2 2
10
0 1 2 3 1 2 3 4 5 7
*/