#include <stdio.h>

long power_mod(long base, long exp, long mod) {
  long result = 1;
  base = base % mod;
  while (exp > 0) {
    if (exp % 2 == 1) result = (result * base) % mod;
    base = (base * base) % mod;
    exp = exp / 2;
  }
  return result;
}

int main() {
  long m = 97;
  long e = 17, d = 2753, n = 3233;
  long sig = power_mod(m, d, n);
  printf("signature   = %ld\n", sig);
  long check = power_mod(sig, e, n);
  printf("verified as = %ld\n", check);
  if (check == m) printf("signature valid\n");
  else printf("signature INVALID\n");
  return 0;
}