#include <stdio.h>
#include <gmp.h>
#define GODFREY 0
#if GODFREY
  #define CHECK_BIT(var,pos) (((var) & (pos)) ? 1LL : -1LL)
#else
  #define CHECK_BIT(var,pos) (((var) & (pos)) ? 1LL : 0LL)
#endif
#define n 9


int count_bits(unsigned x) {
   x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
   x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
   x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
   x = (x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF);
   return x&1;
}

int main()
{
  mpz_t bigsum;
  mpz_t tmp;
  unsigned long long int x, sum, swp;
  unsigned int j, k, odd;
  long long int prod[n];
  mpz_init(bigsum);
  mpz_init(tmp);
  for (j=0; j < n; j++) prod[j] = 0LL;
  for(x=0; x < (1LL<<(2*n)); x++)
  {
    for (k=1; k <= n; k++)
    {
      sum = 0LL;
      swp = 1LL;
      for(j=1; j <= (2*n-k); j++, swp<<=1)
      {
	sum += CHECK_BIT(x,swp)*CHECK_BIT(x,swp<<k);
      }
      prod[k-1] = sum;
    }

    mpz_set_si(tmp, prod[0]);
    for (j=1; j<n;j++) 
      mpz_mul_si(tmp, tmp, prod[j]);

    if(count_bits(x)) mpz_sub(bigsum,bigsum,tmp);
    else mpz_add(bigsum,bigsum,tmp);
  }
  #if GODFREY
    mpz_div_ui(bigsum, bigsum, (1LL<<2*n));
  #endif
  gmp_printf("Skolem sequences of order %d: %Zd\n", n, bigsum);
}