s=open(0).read()
z=9**9
exec(s[:-9]+['nt(z**-~x%(z*z+~z)%z)','+=n,','pow(q,n-2,n))'][len(s)>>7])