#include <stdio.h>
#include <time.h>

// Python hash() function. Assumes 32-bit int.
// Derived from string_hash() in stringobject.c in Python 2.5.1 sources.
static int py_hash(const char* a, int size)
{
   int len = size;
   const unsigned char* p = (unsigned char*)a;
   int x = *p << 7;
   while (--len >= 0) x = (1000003 * x) ^ *p++;
   x ^= size;
   if (x == -1) x = -2;
   return x;
}

// Simulate python modulo operator. Assumes mod is positive.
static int py_mod(int j, int mod)
{
   int ret;
   if (j >= 0) {
      ret = j % mod;
   } else {
      ret = j - (j / mod) * mod;
      if (ret) ret += mod;
   }
   return ret;
}

int main()
{
   int q0, q1, q2, q3, q4, q5, q6, q7, q8, q9;
   int m, d, c, l, x, v, i;
   char magic[16];
   time_t  tstart = time(NULL);
   clock_t cstart = clock();
   time_t  tend;
   clock_t cend;
   if (sizeof(int) != 4) { fprintf(stderr, "oops sizeof int != 4\n"); return 1; }
   for (q0 = 1; q0 < 128; ++q0) {
    magic[1] = q0;
    for (q1 = 1; q1 < 128; ++q1) {
     magic[2] = q1;
     for (q2 = 1; q2 < 128; ++q2) {
      magic[3] = q2;
      for (q3 = 1; q3 < 128; ++q3) {
       magic[4] = q3;
       for (q4 = 1; q4 < 128; ++q4) {
        magic[5] = q4;
        for (q5 = 1; q5 < 128; ++q5) {
         magic[6] = q5;
         for (q6 = 1; q6 < 128; ++q6) {
          magic[7] = q6;
          for (q7 = 1; q7 < 128; ++q7) {
           magic[8] = q7;
           for (q8 = 1; q8 < 128; ++q8) {
            magic[9] = q8;
            for (q9 = 1; q9 < 128; ++q9) {
             magic[10] = q9;
             magic[0] = 'M'; m = py_mod(py_hash(magic, 11), 1001);
             if (m != 1000) continue;
             magic[0] = 'D'; d = py_mod(py_hash(magic, 11), 1001);
             if (d != 500) continue;
             magic[0] = 'C'; c = py_mod(py_hash(magic, 11), 1001);
             if (c != 100) continue;
             magic[0] = 'L'; l = py_mod(py_hash(magic, 11), 1001);
             if (l != 50) continue;
             magic[0] = 'X'; x = py_mod(py_hash(magic, 11), 1001);
             if (x != 10) continue;
             magic[0] = 'V'; v = py_mod(py_hash(magic, 11), 1001);
             if (v != 5) continue;
             magic[0] = 'I'; i = py_mod(py_hash(magic, 11), 1001);
             if (i != 1) continue;
             printf("bingo! %d %d %d %d %d %d %d %d %d %d\n",
              q0, q1, q2, q3, q4, q5, q6, q7, q8, q9);
            }
           }
          }
         }
        }
       }
      }
     }
    }
   }
   tend = time(NULL);
   cend = clock();
   printf("(wall clock time:%ld secs, cpu time:%.2f units)\n",
      (long)   (difftime(tend, tstart)+0.5),
      (double) (cend-cstart) / (double)CLOCKS_PER_SEC);
   return 0;
}