#include <stdio.h>
#include <math.h>

/* By J. Cisneros and S. J. Miller, May 2001 */
/* This program is for p congruent 1 mod 3)  */

void main()
{
  long a3, b3, c3, d3, e3, f3;
  double counter=0;
  int counter3=0;
  double p5;
  int p;
  long z, q;
  int x,y,i,j,num,root, root3;
  int pp, q3, z3;
  int fact[7];
  int a[7], n[14];
  int va[100];  

  fact[1] = 1; fact[2] = 2; fact[3] = 6;
  fact[4] = 24; fact[5] = 120; fact[6] = 720;


  /* the above initializes fact[], an array which */
  /* stores the values of the first 6 factorials, */
  /* namely, fact[x] = x! This will be used to    */
  /* count permutations below.                    */

  p = 373;
  pp = (p-1) / 3;
  root = 5;
  root3 =root*root*root % p;
  
  
  va[0] = 0; va[1] = (root*root*root) % p;
  for (x = 2; x <= pp; ++x)
    {
      va[x] = va[x-1]*root3 % p;
    }
  //  for (x = 0; x <= pp; ++x) printf("x = %d, x^3 = %d\n", x, va[x]); //
   

  /* a[] is an array of six values, a[1], ..., a[6] */
  /* these are our 6 loop variables. it's easier    */
  /* writing like this as opposed to a,b,...,f as   */
  /* it is easy to refer to each one.               */

  /* to dramatically increase runtime, we notice:   */
  /* (1) instead of studying a^3 + b^3 + c^3 -      */
  /*     (d^3 + e^3 + f^3) study a^3 + ... + f^3    */
  /*     Why? Mod p, e and -e range thru the same   */
  /*     values, so can change variables e --> -e   */
  /* (2) wlog, let a >= b >= c >= d >= e >= f, and  */
  /*     then count permutations.                   */
  /* a = a[1], b = a[2], of course....              */

  for (a[1]=0; a[1]<= pp; a[1]++)
    { a3 = va[a[1]];

    for (a[2]=0; a[2]<=a[1]; a[2]++)
      { b3 = va[a[2]];

      for (a[3]=0; a[3]<=a[2]; a[3]++)

        { c3= va[a[3]];

	for (a[4]=0; a[4]<=a[3]; a[4]++)
	  { d3 = va[a[4]];

	  for (a[5]=0; a[5]<=a[4]; a[5]++)
	    { e3 = va[a[5]];

	    for (a[6]=0; a[6]<=a[5]; a[6]++)
	      { f3 = va[a[6]] ;
                   
	      z3 = a3 + b3 + c3 + d3 + e3 + f3;
	      q3 = z3 % p;

	      for (x = 1; x <= 6; ++x) n[x] = 1;
	      i = 2;
	      while (a[i] == a[1]) { n[1]++; i++;}
	      j = i+1;
	      while (a[j] == a[i]) { n[i]++; j++;}
	      i = j+1;
	      while (a[i] == a[j]) { n[j]++; i++;}
	      j = i+1;
	      while (a[j] == a[i]) { n[i]++; j++;}
	      i = j+1;
	      while (a[i] == a[j]) { n[j]++; i++;}
	      j = i+1;
	      while (a[j] == a[i]) { n[i]++; j++;}

	      num = 720 / (fact[n[1]]*fact[n[2]]*fact[n[3]]*
			   fact[n[4]]*fact[n[5]]*fact[n[6]]);
	      for (j = 1; j <= 6; ++j)
		{
		  if (a[j] != 0) num = num*3;
		}

	      /* the above figures out how many permutations */
	     
	      //printf("a = %d\n", f3);//
	      //printf("z = %d\n", z);//
	      //printf("q = %d\n", q);//

	      if (q3==0) counter3 = counter3 + num;
	      }
	    }
	  }
        }
      }
    }

  printf("cube counter = %d\n", counter3);
}


/* the below are for the purposes of debugging, some values of   */
/* running earlier versions of this program (where each variable */
/* goes from 0 to p-1). our version should, and does, match.     */
/*
  p = 29 cube counter = 20511149

  p = 23 cube counter =  6436343

  p = 17 cube counter =  1419857

  p = 11 cube counter =   161051

  p =  7 cube counter =    22141
*/

/* results of running j6.c    */
/* p = 101                    */  
/* cube counter = 1920165909  */
/* p^5 =         10510100501  */
/* 13mins33secs               */