// This version of the code uses a static array of counts for it seems that
// megabyte stackframes are queasy.
// This version seems to work.
// Link with code at http://cap-lore.com/code/shran.c
#include <stdio.h>
#include <stdlib.h>
typedef unsigned int u32;
typedef struct{u32 st[5]; int bc;} prngS; // Don't peek!
int Rand(prngS *, int n);
prngS gg(long long);
#define prec 6
typedef unsigned short uc;
typedef struct{u32 a[prec];} b;
#define C const
prngS rss;
static b sri(C b z){b x; int j, k; for(j=0; j<prec; ++j) {
    if(z.a[j]) goto vn; x.a[j] = 0;}
  printf("Can't be zero\n"); exit(3);
  vn: for(k=27; k>=0; --k) if(z.a[j] & (1<<k)) break;
  while(1){
b fill(int n){
   for(n = n+1; n < prec; ++n) x.a[n] = Rand(&rss, 28); return x;}
    x.a[j] = Rand(&rss, k+1);
    if (x.a[j] < z.a[j]) return fill(j);
    if (x.a[j] > z.a[j]) goto more;
    {int m; for(m = j+1; m < prec; ++m) {x.a[m] = Rand(&rss, 28);
      if (x.a[m] > z.a[m]) goto more;
      if (x.a[m] < z.a[m]) return fill(m);}}
more: ;
}}

static void addTo(b* x, b* y) {int j = prec, c=0; while(j--) {
  int q = x->a[j] + y->a[j] + c;
  c = q>>28; x->a[j] = q & ((1<<28)-1);}
  if(c) {printf("Overflow\n"); exit(3);}}
static void subFrm(b* x, b* y) {int j = prec, c=0; while(j--) {
  int q = x->a[j] - y->a[j] - c;
  if(q<0) {x->a[j] = q + (1<<28); c = 1;}
  else {x->a[j] = q; c = 0;}}
  if(c) 
  {printf("Underflow\n"); exit(3);}}
static int div10(b* x){int c = 0, j; for(j=0; j<prec; ++j){
  u32 n = (c<<28) + x->a[j]; x->a[j] = n/10; c =  n%10;}
  return c;}
static 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]);}
static b sb(int j){b x; int k=prec; while(k--) x.a[k]=0; x.a[prec-1] = j; return x;}
static b s2b(char * s){b x; {int j=prec; while(j--) x.a[j]=0;}
  while(*s){char d = *s; if(d < '0' || d > '9') {printf("non digit!\n"); exit(3);}
    addTo(&x, &x);
    {b y = x; addTo(&y, &y); addTo(&y, &y); addTo(&x, &y);}
    {b y = sb (d - '0'); addTo(&x, &y); ++s;}} return x;}
static int less(b*x, b*y) {int j; for(j=0; j<prec; ++j)
if(x->a[j] < y->a[j]) return 1;
 else if(x->a[j] > y->a[j]) return 0;
 return 0;}

#define pxc 2700
#define sz 16
static b szs[sz][pxc];
static int fbex;
static uc pats[pxc];

static void ps(char * s){int j, k; for(k=0; k<sz; ++k) {for(j=0; j<fbex; ++j)
     printf("%04d", szs[k][j].a[prec-1]);
    printf(" %s\n", s);}}

static void fp(b ch, uc * w){int n = sz; uc rp = 0;
while(n--) {int k = fbex; b s = sb(0); while(k--)
  if(!(rp & pats[k])) {addTo(&s, &szs[n][k]); if(less(&ch, &s)) break;}
   if(k<0) {printf("Input too big: not that many solutions\n"); exit (3);}
   subFrm(&s, &szs[n][k]); subFrm(&ch, &s); rp = pats[k]; w[n] = rp;}}
static void fpx(b ch){uc x[sz]; fp(ch, x); pr(ch); printf("\n");
  {int j=sz; while(j--) {printf("%04X ", x[j]); 
  {int k=sz; while(k--) printf((x[j]>>k)&1?"* ":"  ");}
  printf("\n");}}}

int main(){
int fa=1, fb=1;
{int j=sz; while(j--) {int t = fa; fa = fb; fb += t;} fbex = fb;}
if(fb > pxc) {printf("Foo\n"); exit(3);}
rss = gg(43);
{b b0 = sb(0), b1 = sb(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);}}
 {int j=fb; while(j--) szs[0][j] = b1;}
 {int j; for(j=1; j<sz; ++j) 
  {int n = fb; while(n--)
    {int k = fb; b s = b0; while(k--)
        if(!(pats[n] & pats[k])) addTo(&s, &szs[j-1][k]);
      szs[j][n] = s;}}}
  {b s = b0; {int j=fb; while(j--) addTo(&s, &szs[sz-1][j]);}
  // 10000000000000000000000026945799438770091650189
  
   if(1) while(1) {printf("Enter a numeral from 0 to ");
     pr(s); printf("\n");
     int j=0; char in[51];
     while(1) {char c = getchar();
       if (c == '\n') {in[j]=0; break;}
       else if(j==51) {printf("Too long\n"); exit(4);}
       else in[j++] = c;}
     fpx(s2b(in));}
   if(0) {int j=5; while(j--) fpx(sri(s));}
   if(0) {int cc[sz][sz]; {int j=sz; while(j--){int k=sz; while(k--) cc[j][k]=0;}}
      {int j=100000; while(j--) {uc a[sz]; fp(sri(s), a);
        {int j=sz; while(j--){int k=sz; while(k--) if(a[j] & (1<< k)) ++cc[j][k];}}}}
    {int j=sz; while(j--){int k=sz; while(k--) printf(".%5d ", cc[j][k]);
       printf("\n");}}}}}
return 0;}