#include <stdio.h>
#include <stdlib.h>
#define prec 6
typedef unsigned short uc;
typedef struct{unsigned int a[prec];} b;
void addTo(b* x, b* y) {int j = prec, c=0; while(j--) {
  int q = x->a[j] + y->a[j] + c;
  if(q>=(1<<28)) {x->a[j] = q - (1<<28); c = 1;}
  else {x->a[j] = q; c = 0;}}
  if(c) exit(printf("Overflow\n"));}
int div10(b* x){int c = 0, j; for(j=0; j<prec; ++j){
  unsigned int n = (c<<28) + x->a[j]; x->a[j] = n/10; c =  n%10;}
  return c;}
void pr(b x){char d[51]; int j = 51; while(j--) d[j] = div10(&x) + '0';
  for(j=0; j<51; ++j) putchar(d[j]);}

int main(){
// -1 0 1 2 3 4  5  6  7  8  9  10  11  12  13  14   15   16
//  1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584
int fa=1, fb=2, sz;
for(sz = 1; sz<17; ++sz) {
uc pats[fb];
b b0, b1;
{int j=prec; while(j--) b0.a[j] = b1.a[j] = 0; b1.a[prec-1]=1;}
{int j = 1<<sz, x = 0; while (j--) if(!(j & (j<<1))) pats[x++] = j;
  if (x != fb) {printf("zilch %d %d %d\n", x, sz, fb); exit (3);}}
 {b old[fb], new[fb]; int height=sz-1;
 {int j=fb; while(j--) old[j] = b1;}
 while (height--)
 {int k = fb; {int n = fb; while(n--) new[n] = b0;}
   while(k--) {int n = fb;
     while(n--) if(!(pats[n] & pats[k])) addTo(new+n, old+k);}
   {int n = fb; while(n--) old[n] = new[n];}}
  if(0){int j=fb; while(j--) {pr(old[j]); printf(" %04X\n", pats[j]);}}
{int j=fb; b s = b0; while(j--) addTo(&s, old+j);
  pr(s); printf(" %d square patterns All together\n", sz);}
}
{int t = fa; fa = fb; fb += t;}}
if(fb != 2584+1597) printf("Corruption!!\n");
return 0;}

/* Yields for totals:
 1 -> 2
 2 -> 7
 3 -> 63
 4 -> 1234
 5 -> 55447
 6 -> 5598861
 7 -> 1280128950
 8 -> 660647962955
 9 -> 770548397261707
10 -> 2030049051145980050
11 -> 12083401651433651945979
12 -> 162481813349792588536582997
13 -> 4935961285224791538367780371090
14 -> 338752110195939290445247645371206783
15 -> 52521741712869136440040654451875316861275
16 -> 18396766424410124752958806046933947217821482942
*/