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