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

unsigned long long P,Q,E,D;

int ExtendedGCD(long long A,long long B, long long *C, long long *D)
{
    int I;
    long long J;
    if (A%B==0)
    {
        (*C)=0;
        (*D)=1;
        return B;
    }
    else
    {
        I = ExtendedGCD(B,A%B,C,D);
        J=(*C);
        (*C)=(*D);
        (*D)=(*D)*(-A/B)+J;
        return I;
    }
}

void GenerateKeys()
{
    long long I,J;
    P=6469;  /*944659*/
    Q=5431;  /*817907*/
    E=65537;
    ExtendedGCD((P-1)*(Q-1),E,&I,&J);
    while (J<=0)
        J+=(P-1)*(Q-1);
    D=J;
}

unsigned long long ExponentBySquaring(unsigned long long V,unsigned long long Exp)
{
    unsigned long long I;
    if (Exp==0)
    {
        return 1;
    }
    else if (Exp==1)
    {
        return V%(P*Q);
    }
    else
    {
        if (Exp%2==0)
        {
            I=ExponentBySquaring(V,Exp/2);
            I=(I*I)%(P*Q);
        }
        else
        {
            I=ExponentBySquaring(V,Exp/2);
            I=((I*I)%(P*Q))*(V%(P*Q));
        }
        return I%(P*Q);
    }
}

unsigned long long MyEncrypt(unsigned long long M)
{
    return ExponentBySquaring(M,E);
}

unsigned long long MyDecrypt(unsigned long long C)
{
    return ExponentBySquaring(C,D);
}

int main()
{
    GenerateKeys();
    printf("%llu\n",MyDecrypt(MyEncrypt(65)));
    return 0;
}