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

// modexp 0857bde36f680cda9535784bc4aec5f4344131071b419f732ac9c74d0e61db49dd958c7344236e0279df009c6e66aec6ba574c2820d4aeb0c4d814c8e184c6ea7e6d8aa3e15d1c251c78c5364ea2b3edb3c19e90739afa765506242e78fcdc71a87efdfe2df6ce6039fc62cb3b360cb77cd5574292282df352886cbc3fcfbff2 10001 F765A3A0C9C291D81A56FE73794A746B8DA23DBE155D0D495B49D581B5C6545F449A10FDF1C26A92FBD1F43A0687044927A6A21B69A73999E6083D03ACDAFFA6409F1BC71D810628F6E18F76231ED6E22D54ED2502E66F8A33D0D5F07B3EB605F7418110E2EF9A5EE77B070F4EADFCF3D70C53E870F29C9D4F229F2CB6C25383

typedef unsigned char num_t;
// all numbers are stored least significant byte first.
// all numbers contain a number of max len, and have space for 1 extra byte

void writenum(const num_t *num, int len);

void rightshift(num_t *val, int len)
{
    int carry= 0;
    for (int i=len-1 ; i>=0 ; i--)
    {
        carry |= val[i];
        val[i]= carry>>1;
        carry &= 1;
        carry <<= 8;
    }
}
void leftshift(num_t *val, int len)
{
    int carry= 0;
    for (int i=0 ; i<len ; i++)
    {
        carry |= val[i]<<1;
        val[i]= carry;
        carry >>= 8;
        carry &= 1;
    }
}
void big_add(num_t *sum, const num_t *val, int len)
{
    int carry=0;
    //writenum(sum, len); printf(" + "); writenum(val, len);
    for (int i=0 ; i<len ; i++)
    {
        carry += sum[i] + val[i];
        sum[i]= carry;
        carry >>= 8;
    }
    //printf(" = "); writenum(sum, len); printf("\n");
}
void big_sub(num_t *sum, const num_t *val, int len)
{
    int carry=0;
    //writenum(sum, len); printf(" - "); writenum(val, len);
    for (int i=0 ; i<len ; i++)
    {
        //printf("%x+%x-%x", carry, sum[i], val[i]);
        carry += sum[i] - val[i];
        sum[i]= carry;
        carry >>= 8;
        //printf("=%x:%x\n", carry, sum[i]);
    }
    //printf(" = "); writenum(sum, len); printf("\n");
}
void modtrunc(num_t *val, const num_t *mod, int len)
{
    //printf("modtrunc "); writenum(val, len); printf(" : "); writenum(mod, len); printf("\n");
    int i=len-1;
    while (i>0 && val[i]==mod[i]) {
        i--;
    }
    if (val[i]>=mod[i]) {
        //printf("mod trunc %d: %02X >= %02X\n", i, val[i], mod[i]);
        big_sub(val, mod, len);
    }
}
void big_mulmod(num_t *val, const num_t *mult, const num_t *mod, int len)
{
    //printf("calc mulmod "); 
    //writenum(val, len); printf(" x ");
    //writenum(mult, len); printf(" mod "); 
    //writenum(mod, len); printf("\n");

    num_t *bits=(num_t*)alloca(len); memcpy(bits, val, len);
    num_t *lshifter=(num_t*)alloca(len+1); memcpy(lshifter, mult, len);
    lshifter[len]=0;
    memset(val, 0, len);

    for (int i=0 ; i<len*8 ; i++)
    {
        if (bits[0]&1) {
            big_add(val, lshifter, len);
            modtrunc(val, mod, len);
        }
        //printf("   bits="); writenum(bits, len); printf(" ");
        //printf("   lsh=");  writenum(lshifter, len); printf(" ");
        //printf("   val=");  writenum(val, len); printf("\n");
        rightshift(bits, len);
        leftshift(lshifter, len);
        modtrunc(lshifter, mod, len);
    }
    //printf("mulmodresult="); writenum(val, len); printf("\n");
}

bool big_bittest(const num_t* num, int bit)
{
    return num[bit/8]&(1<<(bit&7));
}
void modexp(const num_t *num, const num_t *exp, int explen, const num_t *modulus, num_t *result, int len)
{
    //printf("calc modexp "); 
    //writenum(num, len); printf(" ^ ");
    //writenum(exp, explen); printf(" mod "); 
    //writenum(modulus, len); printf("\n");

    num_t *num2= (num_t*)alloca(len);
    memset(num2, 0, len);
    num2[0]= 1;
    big_mulmod(num2, num, modulus, len); // num2 = (num2*num) % modulus


    memset(result, 0, len);
    result[0]=1;

    for (int expbit=0 ; expbit<explen*8 ; expbit++) {
        //printf("%d: num2=", expbit); writenum(num2, len); printf("\t");
        //printf("result="); writenum(result, len); printf("\n");
        if (big_bittest(exp, expbit)) {
            big_mulmod(result, num2, modulus, len);
            //printf(" ***");
        }
        //printf("\n");
        big_mulmod(num2, num2, modulus, len);  // num2 = (num2*num2) % modulus
    }
    //printf("modexpresult="); writenum(result, len); printf("\n");
}
int digit2val(char c)
{
    return c<='9' ? c-'0'
            : c<='F' ? c-'A'+10
            : c<='f' ? c-'a'+10
            :0;
}
void hexstr2num(num_t *num, int len, const char* hexstr)
{
    int j=0;
    for (int i=strlen(hexstr)-1 ; i>=0 ; i--, j++) {
        if (j&1) {
            num[j/2] |= digit2val(hexstr[i])<<4;
        }
        else {
            num[j/2] = digit2val(hexstr[i]);
        }
    }
    if (j&1) j++;
    j/=2;
    while (j<len)
        num[j++]=0;
}
void writenum(const num_t *num, int len)
{
    int i=len-1;
    while (num[i]==0 && i>0) i--;
    while (i>=0)
    {
        printf("%02X", num[i]);
        i--;
    }
}
int main(int argc, char **argv)
{
    if (argc!=4) {
        printf("Usage: modexp num exp mod\n");
        return 1;
    }
    char *numstr= argv[1];
    char *expstr= argv[2];
    char *modstr= argv[3];

    // strip leading zeros
    while (*numstr=='0') numstr++;
    while (*expstr=='0') expstr++;
    while (*modstr=='0') modstr++;

    int numlen= strlen(numstr)/2+2;
    int explen= strlen(expstr)/2+2;
    int modlen= strlen(modstr)/2+2;
    if (numlen>modlen) {
        printf("number cannot be larger than mod\n");
        return 1;
    }

    int len= modlen;

    num_t *num= (num_t*)alloca(len);
    num_t *exp= (num_t*)alloca(explen);
    num_t *mod= (num_t*)alloca(len);
    hexstr2num(num, len, numstr);
    hexstr2num(exp, explen, expstr);
    hexstr2num(mod, len, modstr);

    //printf("num="); writenum(num, len); printf("\n");
    //printf("mod="); writenum(mod, len); printf("\n");
    //printf("exp="); writenum(exp, explen); printf("\n");

    num_t *result= (num_t*)alloca(len);

    modexp(num, exp, explen, mod, result, len);

    writenum(result, len);
    printf("\n");
}