a = 45880
b = 92678

g = 672378890

import math
d = dict()
for x in range(100, 10 ** 5 + 1):
	k = math.gcd(b, math.gcd(g, x))
	d[k] = pow(x, a, b)

print(a, b)
k = int(input())
k = math.gcd(k, b)
print(d[k])

ret = int(input())