exec"a,b,m=0,1,10**9\nfor i in bin(input())[2:]:c=a*a+b*b;d=a*b*2+b*b;a,b=[d-c,c%m,d%m][int(i):][:2]\nprint b;"*9