#include <stdio.h>
#include "util.h"

int K;

unsigned short hist[32768];

# define MAXHIST 60000

# define S(n) s/**/n
# define D(n) unsigned short S/**/n[n]
# define I(n) { int i; for (i = 0; i < n; i++) S/**/n[i] = 0; }
# define H(n) { int i; clear_hist(); \
                for (i = 0; i < n; i++) { \
		    unsigned short k = S/**/n[i]; hist[k] += (hist[k] < MAXHIST) ? 1 : 0;} \
                report_hist(n); }
# define U(n)  S/**/n[h % n]++

# define DO(M) M(255); M(257); M(1023); M(1024); M(1025); M(4095); M(4096); M(4097); M(16383); M(16384); M(16385)

DO(D);

clear_stats() 
{
  DO(I);
}

report_hist(n)
{
  int i;
  printf("For hashes mod %d\n", n);
  for (i = 0; i < 32768; i++)
    if (hist[i] > 0) printf("Hist[%d] = %d\n", i, hist[i]);
}

clear_hist()
{
  int i;
  for (i = 0; i < 32768; i++)
    hist[i] = 0;
}

main()
{
  int rc = scanf("%d", &K);

  while (rc == 1)
    {
      test_a_hash();
      rc = scanf("%d", &K);
    }

}

UINT   local_hash(s) unsigned char * s; {
       UINT i = 0;
       while (*s != 0) {
           i = i * K + *s++;
           }
       return i;
       }

test_a_hash()
{
  int rc;
  FILE * fd = fopen("/usr/dict/words", "r");
  char s[256];

  clear_stats();

  rc = fscanf(fd, " %s", s);
  while (rc == 1)
    {
      unsigned int h = local_hash(s);
      DO(U);
      rc = fscanf(fd, " %s", s);
    }
  fclose(fd);
  DO(H);
}

hash1(s) unsigned char * s; {
  unsigned int i = 0;
  while (*s != 0) {
    register unsigned int Rb, Ra = i;

    /* Rb = i * 270566475 */
    Rb = Ra + (Ra << 4); /* step 4, shift 4 */
    Rb = (Rb << 4) - Ra; /* step 5, shift 4 */
    Rb = (Rb << 6) + Rb; /* step 1, shift 6 */
    Rb = Ra + (Rb << 8); /* step 4, shift 8 */
    Rb = Ra + (Rb << 2); /* step 4, shift 2 */
    Rb = (Rb << 4) - Rb; /* step 2, shift 4 */
    
    i = Rb + *s++;
  }
  return i;
}

hash2(s) unsigned char * s; {
  unsigned int i = 0;
  while (*s != 0) {
    register unsigned int Rb, Ra = i;

    /* Rb = i * 1431655765 */
    Rb = Ra + (Ra << 2); /* step 4, shift 2 */
    Rb = (Rb << 4) + Rb; /* step 1, shift 4 */
    Rb = (Rb << 8) + Rb; /* step 1, shift 8 */
    Rb = (Rb << 16) + Rb; /* step 1, shift 16 */
    i = Rb + *s++;
  }
  return i;
}

hash3(s) unsigned char * s; {
  unsigned int i = 0;
  while (*s != 0) {
    register unsigned int Rb, Ra = i;

    Rb = Ra * 135283237;

    i = Rb + *s++;
  }
  return i;
}