m=10**9 while 1: a,b,n=0,1,input()+1 for x in bin(n)[2:]:c,d=(a*b*2-a*a)%m,(a*a+b*b)%m;a,b=((c,d),(d,c+d))[int(x)] print a
Note that non-ascii characters in the above source code will be escaped (such as \x9f).
download
return to the top page