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

long long P, Q, E, D;

long long ExtendedGCD(long long A, long long B, long long *C, long long *D)
{
	long long 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 = 944659;
	P = 10007;
	Q = 817907;
	Q = 10009;
	E = 65537;
	ExtendedGCD((P - 1)*(Q - 1), E, &I, &J);
	while (J <= 0)
		J += (P - 1)*(Q - 1);
	D = J;
}

long long ExponentBySquaring(long long V, long long Exp)
{
	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 % (P*Q)) * (I % (P*Q))) % (P*Q);
		}
		else
		{
			I = ExponentBySquaring(V, Exp / 2);
			I = ((((I % (P*Q)) * (I % (P*Q))) % (P*Q))*(V % (P*Q))) % (P * Q);
		}
		return I % (P*Q);
	}
}



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

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

int main()
{
	GenerateKeys();
	printf("%lld\n", MyDecrypt(MyEncrypt(65)));
	while (getchar() != 'q')
	{

	}
	return 0;
}