#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <iostream>
#include <gmpxx.h>
#include <map>
#ifndef NDEBUG
#define ASSERT(x) assert(x)
#else
#define ASSERT(x)
#endif
using namespace std;
typedef map<unsigned long long, mpz_class> IDMap;//mapping id to count

IDMap id_maps1, id_maps2;
IDMap *id_maps_old, *id_maps_new;

void swap_map()
{
    IDMap *tmp = id_maps_old;
    id_maps_old = id_maps_new;
    id_maps_new = tmp;
    id_maps_new->clear();
}

void add_count(unsigned long long c, const mpz_class& cc)
{
    IDMap::iterator it = id_maps_new->find(c);
    if(it==id_maps_new->end()){
       (*id_maps_new)[c]=cc;
    }else{
       (*id_maps_new)[c]+=cc;
    }
}

void move_next_row(int n)
{
    swap_map();
    IDMap::iterator it;
    for(it=id_maps_old->begin();it!=id_maps_old->end();++it){
         unsigned long long the_id=it->first;mpz_class& cc=it->second;
         the_id <<=2;
         (*id_maps_new)[the_id]=cc;
    }
}

void move_next_diag(int row, int n);
int get_tcount(int n, mpz_class& tcount, mpz_class& udcount, mpz_class& ctcount);
int get_diagcount(int n,mpz_class& dcount);
int get_rotatecount(int n,mpz_class& rtcount);
void std_update(int row, int col, int n, int in_half, int dump=0);
#define MAXN 31
#define STATUS(id, index)  (((id)>>(2*(index)))&3)
#define RESET_STATUS(id, index) ((id)&=~(3ll<<(2*(index))))
#define SET_STATUS(id, index, x) (RESET_STATUS(id,index),(id)|=((x)<<(2*(index))))
int get_count_map(unsigned long long y, int n, char map[MAXN+1]);

int main(int argc, char * argv[])
{
    int n, row, col;
    n=atoi(argv[1]);
    if(n>MAXN||n<=1){
       fprintf(stderr,"Input n out of range, it should be in 2..%d\n",MAXN);
       return -1;
    }
    mpz_class tcount,udcount,rtcount,dcount,ccount;
    int r = get_tcount(n, tcount,udcount,ccount);
    get_diagcount(n,dcount);
    get_rotatecount(n,rtcount);
    cout<<"tcount:"<<tcount<<",udcount:"<<udcount<<",ccount:"<<ccount;
    cout<<",dcount:"<<dcount<<",rtcount:"<<rtcount<<'\n';
    mpz_class sum = tcount+2*(udcount+dcount+rtcount)+ccount;
    if(sum%8!=0){
       fprintf(stderr,"Algorithm error\n");
       return -1;
    }
    cout<<"A200000:"<<sum/8<<",A200749:"<<tcount<<"\n";
    return 0;
}

int get_diagcount(int n,mpz_class& dcount){
    int row,col;
    dcount=0;
    id_maps1.clear();id_maps2.clear();
    unsigned long long c=0;
    SET_STATUS(c, 1, 1LL);
    id_maps1[c]=1;
    id_maps_old=&id_maps2;id_maps_new=&id_maps1;
    for(row=1;row<n;row++){
       for(col=0;col<row;col++){
          std_update(row, col, n, 1,0);
       }
       move_next_diag(row, n);
    }
    IDMap::iterator it;
    for(it=id_maps_new->begin();it!=id_maps_new->end();++it){
        dcount += it->second;
    }
    return 0;
}

int get_rotatecount(int n, mpz_class& rtcount){
    int row,col;
    char map[MAXN+1];
    rtcount=0;
    if(n&1)return 0;
    id_maps1.clear();id_maps2.clear();
    unsigned long long c=0;
    id_maps1[c]=1;
    id_maps_old=&id_maps2;id_maps_new=&id_maps1;
    for(row=0;row<n/2;row++){
       for(col=0;col<n/2;col++){
           std_update(row, col, n, 0);
       }
       if(row==n/2-1){
          IDMap::iterator it;
          for(it=id_maps_new->begin();it!=id_maps_new->end();++it){
              unsigned long long y=it->first; mpz_class& cc=it->second;
              int i,c=0;
              int start=0;
              int edgecount=get_count_map(y,n,map);
              if((edgecount&1)==0)continue;
              for(i=0;i<n;i++)if(map[i]>=0)break;
              ASSERT(i<n);
              start=i;
              do{
                 i=map[i]; if(i<0)break;
                 i=n-1-i;
                 c++;
                 if(c>edgecount)break;
              }while(i!=start);
              if(i==start&&c==edgecount){
                  rtcount+=cc;
              }
          }
       }
       move_next_row(n);
    }
    return 0;
}


void move_next_diag(int row, int n)
{
    swap_map();
    IDMap::iterator it;
    for(it=id_maps_old->begin(); it!=id_maps_old->end();++it){
       unsigned long long the_id = it->first; mpz_class& cc=it->second;
       unsigned long long y=the_id;
       int idcol = STATUS(the_id, row);
       if(idcol == 0){
          if(row<n-1){
            SET_STATUS(y, row, 1LL);
            add_count(y, cc);
          }
       }else if(idcol == 1){
          if(row <n-1){
            add_count(y, cc);
          }else{
            RESET_STATUS(y, row);
            add_count(y, cc);
          }
       }else if(idcol == 2){
          if(row<n-1){
             add_count(y,cc);
             RESET_STATUS(y, row);
             add_count(y,cc);
            SET_STATUS(y,row, 1LL);
            add_count(y,cc);
          }
       }
    }
    move_next_row(n);
}

void std_update(int row, int col, int n, int in_half, int dump)
{
    swap_map();
    IDMap::iterator it;
    for(it=id_maps_old->begin();it!=id_maps_old->end();++it){
       unsigned long long the_id=it->first; mpz_class& cc=it->second;
       unsigned long long y=the_id;
       int idcol, idcolp1;
       idcol=STATUS(the_id, col);idcolp1=STATUS(the_id, col+1);
       if(idcol!=0&&idcolp1!=0){
          if(idcol==2&&idcolp1==1){
              if(col<n-1&&row<n-1){
                     add_count(y,cc);
              }
              RESET_STATUS(y,col);RESET_STATUS(y,col+1);
              add_count(y, cc);
              if(col<n-1&&row<n-1){
                 SET_STATUS(y,col, 1LL);SET_STATUS(y,col+1,2LL);
                 add_count(y,cc);
              }
          }else if(idcol==1&&idcolp1==1){
              int i,lc=0;
              if(col<n-1&&row<n-1){
                 add_count(y,cc);
              }
              RESET_STATUS(y,col);RESET_STATUS(y,col+1);
              for(i=col+2;i<n+1;i++){
                  if(STATUS(y,i)==1)lc++;
                  else if(STATUS(y,i)==2){
                      if(lc==0)break;
                      else lc--;
                  }
              }
              ASSERT(in_half||i<n+1);
              if(i<n+1){
                  SET_STATUS(y,i,1LL);
                  add_count(y,cc);
                  if(col<n-1&&row<n-1){
                    SET_STATUS(y, col, 1LL); SET_STATUS(y, col+1, 2LL);
                    add_count(y,cc);
                  }
              }
          }else if(idcol==2&&idcolp1==2){
              if(col<n-1){
                 add_count(y, cc);
              }
              RESET_STATUS(y,col);RESET_STATUS(y,col+1);
              int i,twoc=0;
              for(i=col-1;i>=0;i--){
                 if(STATUS(y,i)==2)twoc++;
                 else if(STATUS(y,i)==1){
                    if(twoc==0)break;
                    else twoc--;
                 }
              }
              ASSERT(i>=0);
              SET_STATUS(y,i,2LL);
              add_count(y,cc);
              if(col<n-1&&row<n-1){
                 SET_STATUS(y,col, 1LL);SET_STATUS(y,col+1, 2LL);
                 add_count(y,cc);
              }
          }else if(idcol==1&&idcolp1==2){//only for last cell
              if(col==n-1&&row==n-1){
                   RESET_STATUS(y,col);
                   RESET_STATUS(y,col+1);
                   add_count(y,cc);
              }else{
                   if(col<n-1&&row<n-1){
                       add_count(y,cc);
                   }
             }
          }
        }else if(idcol>0||idcolp1>0){//only one edge used
              unsigned long long cur=idcol+idcolp1;//one of them is 0.
              if(row<n-1){
                     SET_STATUS(y,col,cur);
                     RESET_STATUS(y,col+1);
                     add_count(y,cc);
              }
              if(col<n-1){
                     RESET_STATUS(y,col);
                     SET_STATUS(y,col+1,cur);
                     add_count(y,cc);
              }
        }else{
                  if(row<n-1&&col<n-1){
                     SET_STATUS(y,col,1LL);SET_STATUS(y,col+1,2LL);
                     add_count(y,cc);
                  }
       }
   }
}

int get_count_map(unsigned long long y, int n, char map[MAXN+1])
{
    int i;
    int prev=-1;
    int count=0;
    for(i=0;i<n;i++){
         if(STATUS(y,i)==0)map[i]=-1;
         if(STATUS(y,i)==1){
             count++;
             map[i]=prev;prev=i;
         }else if(STATUS(y,i)==2){
             ASSERT(prev!=-1);
             map[i]=prev;prev=map[prev];map[map[i]]=i;
         }
    }
    ASSERT(prev==-1);
    return count;
}

int get_tcount(int n, mpz_class& tcount, mpz_class& udcount, mpz_class& ctcount){
    int row, col;
    char map[MAXN+1];
    id_maps1.clear();id_maps2.clear();
    unsigned long long c=0;//init status, no out edges
    udcount=tcount=ctcount=0;
    id_maps1[c]=1;
    id_maps_old=&id_maps2;id_maps_new=&id_maps1;
    for(row=0;row<n;row++){
        for(col=0;col<n;col++){
             std_update(row, col,n, 0);
             if((n&1)&&row==n/2&&col==n/2-1){
                 IDMap::iterator it;
                 mpz_class total=0;
                 for(it=id_maps_new->begin();it!=id_maps_new->end();++it){
                    unsigned long long y=it->first; mpz_class& cc=it->second;
                    if(STATUS(y,col+1)==0||STATUS(y,col+2)==0)continue;
                    int edge_count=get_count_map(y,n+1,map);
                    int i, start;
                    start=col+1;i=0;
                    if(edge_count==0)continue;
                    do{
                      int end = map[start];if(end<0)break;
                      if(end==col+1||end==col+2){
                           ASSERT(end!=col+1);
                           if(i+1==edge_count){
                               //found solution
                               total+=cc;
                           }
                           break;
                      }
                      i++;start=n-end;
                      if(i>edge_count)break;
                    }while(1);
                 }
                 ctcount=total;
             }
        }
        if((n&1)==0&&(row==n/2-1)){//finished half of the row, try to count for *udcount
           IDMap::iterator it;
           mpz_class total = 0;
           for(it=id_maps_new->begin();it!=id_maps_new->end();++it){
               unsigned long long y=it->first; mpz_class& cc=it->second;
               int i,c=0;
               for(i=0;i<n;i++){
                   if(STATUS(y,i)!=0)c++;
               }
               if(c==2){
                   total+=cc;
               }
           }
           udcount=total;
           total=0;
           for(it=id_maps_new->begin();it!=id_maps_new->end();++it){
               unsigned long long y=it->first; mpz_class& cc=it->second;
               int edge_count = get_count_map(y,n, map);
               if((edge_count&1)==0)continue;
               int start=0;while(map[start]<0)start++;//find start node
               int i=start,c=0;
               do{
                    i=map[i];if(i<0)break;i=n-1-i;c++;
                    if(c>edge_count)break;
               }while(i!=start);
               if(i==start&&c==edge_count){
                   total+=cc;
               }
           }
           ctcount=total;
        }
        move_next_row(n);
    }
    mpz_class total=0;
    IDMap::iterator it;
    for(it=id_maps_new->begin();it!=id_maps_new->end();++it){
        total += it->second;
    }
    tcount=total;
    swap_map();
    return 0;
}