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