while 1:
 a=m=10**9;b=1
 for c in bin(input()):
	a,b=a*a+b*b,b*(2*a+b)%m
	if'1'!=c:a=b-a%m;b-=a
 print b