#!ruby -na
f=->x,s,m{n=o=m
r=i=1
(o%i<1&&n-=n/i
o/=i while o%i<1)until o<i*i+=1
i=x>1?f[x-1,s,n-=n/o%n]+n :s
(i%2>0&&r*=s
s*=s%m
i/=2)while i>0
r%m}
i=j=1
eval'i+=1while j!=j=f[i,%s,%s]'%$F
puts [i,j]*' '