pr,*l,q=print,0 N=n=1 exec(''.join(open(0))[:~9]+"(pow(q,-2%n,n)or q);q,N=N,q+N;l+=n,")