#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>


int main(int ac, char **av) {
  mpz_t base, exp, mod, res, known;
  int cmp;
  
  mpz_init(base);
  mpz_init(exp);
  mpz_init(mod);
  mpz_init(res);
  mpz_init(known);
  
  mpz_set_str(base,
              "09C98FCB9C40EC96BB9ECE3FD053D8468614D2C262A6ED7ACC613968CAF8A58FA725"
              "E113CCB16A000BF82170353B71789E23DD4620966EE23191C97F0290606CB7AEF750CF"
              "9EB6716BB474BA28DD3A615D3FC3D19812ABB2735676C7EBD505497A3080BF349F2833"
              "5439FC0567C150006CE796D9F4307B0A5C0617619C0F4C29CB496D164F09E363A8D535"
              "149B3485D4D0F0C8F2395CBC8E067910CDD9A0228AE6E2E37CA22F75EE91944C231899"
              "A1B340DB9968C6AB1EC7DBA911B0AF3CD3AD1AE83573A51A7DAC53E8FFCBF9D985BE9C"
              "C003409ADB8E068CBE71243C4A4EB678D169489FD0818B91C35F9A073DD2BC06173E13"
              "578481C1E98692B79C0A1CBB", 16);
  
  mpz_set_str(exp,
              "513C8694309772EA44FEA976BE4DD5674F0A798D20385E1F18D71ACA6FD1680D9A09"
              "E9F075BEB7FE8A30911106618A4BC961CC0442E9BB8939D0CB249FEA16ECECB6762ADE"
              "FD1CD660842CDA6CF7EC2EF4C523E61E8F119A1357AF40DAE7E1ECE49F27C23728CD51"
              "86D197802AD03098ACFD8E058BD7F8340FFFB5E8ACB807D7B96D223FB0EC6D6E68C01C"
              "6293BC94B5BD370888C192F9C62C617B1598B8F19914C5F98DBB5B9D06936B5E97BDDE"
              "87FEB0192C9EB0A32D9F7B066D134FB5E9215FF2440340DC33568F5F4441A25F040D81"
              "CF584923A7DF28135F5F30282D344278E60D8DBCB0D36C8641057265406E31896C6BC1"
              "5DB82F0BDAFC5F456C9EB35F", 16);
  
  mpz_set_str(mod,
              "1F8FF0E6C3FF3A40C18BBAB99D9DB19A6413C734507638D6F44B90848D7B4FE2E87E"
              "4D830B14F03E7FD87F47CCD4A715C51839952C5DB5B3F04E4C9633964881B761E763D7"
              "45B5DF2F8649418CB4B3DCA692535B862FC2C62F11DCEE2AB4191B25B35A6DEDC58547"
              "6DACF952A2F580C061F9DCD6C0CE4F08BF401379EC47CED1DE5A3C87EC98CE4DFFC70E"
              "B65A3C6700C5145107D3DD305BA1E0E0F6A957566A0452BE16E39CF4A17185644FBA8E"
              "D1CA79A3D6E28D29D936F2F953913EFBB94B7AF0CAA81CF3F5EF5C86E2F115424FEEEB"
              "D1DAD7FB371E27B2D727381F441ED5377E3DAB15BCF786E88582D6533AF673FA86047E"
              "BBC1667E6A12DD7102359052", 16);
  
  mpz_set_str(known,
              "0FCB1DE435944F516B3F05D990C761985348076167AFCF56FEA05BE1DBA81286BA21"
              "39B0D10232577B79A4B9B872244E966EDC256678D1132B206D357D90F1F601B663DFD6"
              "2FE78449A0D1E4B7E7FC55C2B978282D37B70A6D8715451BC114282B3E9555E23612C2"
              "974974FA52ADDC6F2B030F0E98E6C5C6747C23A58FAE4C8730A37426B54EC604EA1EF1"
              "6F24B1FE8B190A993FC28A95960987D1768AC731DEC4E6B334C75B27589F0E99DAC4A7"
              "AC5CA9E7A014C2E0F05A72A18145A9B8958D0F26E179D3854E3C8CD0C3DD8E11DA318F"
              "9BE873175B1168580CEA42593FEC2795FDBDBC349D10B76118E646AA8EE5C2295452C2"
              "E78DC26528F7C4A4D2F90E21", 16);

  //mpz_powm_sec(res, base, exp, mod);
  mpz_powm(res, base, exp, mod);
  
  mpz_clear(base);
  mpz_clear(exp);
  mpz_clear(mod);
  
  cmp = mpz_cmp(res, known);

  if (cmp == 0) {
    fprintf(stdout, "OK\n");
  } else {
    fprintf(stdout, "SAD: \n");
    mpz_out_str(stdout, 16, res);
  }
  
  mpz_clear(res);
  mpz_clear(known);
  
  fprintf(stdout, "\n");
  
  return 0;
}