#include<bits/stdc++.h>
using namespace std;
int h[75],cnt,poi,po[75],siz[75];
unsigned __int128 ans,m,f[75];
struct did{
    int to,nxt;
}e[155];
void dfs(int x){
    // cout<<x<<" "<<cnt<<"\n";
    siz[x]=1;
    for(int i=h[x],y;i;i=e[i].nxt){
        y=e[i].to;
        dfs(y);
        siz[x]+=siz[y];
    }
}
void print(int x){
    if(x>=10)print(x/10);
    putchar(x%10+'0');
}
void csh(){
    f[1]=1;
    for(int i=1;i<=70;i++){
        for(int j=1;j<i;j++){
            f[i]+=f[j]*f[i-j];
        }
    }
}
unsigned __int128 dp(int x){
    int res=siz[x];
    unsigned __int128 sum=0;
    for(int i=h[x],y;i;i=e[i].nxt){
        y=e[i].to;
        for(int j=1;j<siz[y];j++){
            sum+=f[j]*f[res-j];
        }
        res-=siz[y];
        sum+=dp(y)*f[res];
    }
    return sum;
}
unsigned __int128 encoder(int n, const int *p)
{
    ans=0;
    if(!f[1]){
        csh();   
    }
    for(int i=1;i<=n;i++)h[i]=0;
    for(int i=n;i>=2;i--){
        e[i]={i,h[p[i]]};
        h[p[i]]=i;
    }
    dfs(1);
    return dp(1);
}
int k[75];
void decode(int x,int siz,unsigned __int128 num){
    // cout<<x<<' '<<siz<<"\n";
    while(siz>1){
        int i=1;
        while(1){
            if(num>=f[i]*f[siz-i])num-=f[i]*f[siz-i];
            else{
                po[++cnt]=x;
                decode(cnt,i,num/f[siz-i]);
                num%=f[siz-i];
                siz-=i;
                break;
            }
            i++;
        }
    }
}
void decoder(int n, unsigned __int128 M, int *p)
{
    m=M;
    po[1]=p[1]=0;
    if(n==1)return ;
    cnt=1;
    if(!f[1]){
        csh();   
    }
    decode(1,n,m);
    for(int i=1;i<=n;i++)p[i]=po[i];
    return ;
}
// int main(){
//     int t;
//     cin>>t;
//     while(t--){
//         int n;
//         cin>>n;
//         int a[75],b[75];
//         for(int i=1;i<=n;i++){
//             cin>>a[i];
//         }
//         memset(b,0,sizeof(b));
//         unsigned long long x=encoder(n,a);
//         // print(x);
//         // cout<<'\n';
//         decoder(n,x,b);
//         for(int i=1;i<=n;i++)cout<<b[i]<<"\n";   
//     }
// }
/*
1
31
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
*/