D={}
def f(n):
 n/=2 
 if n<2:D[n]=1
 if n not in D:D[n]=(f(-~n)*f(n)+f(~-n)*f(n-2))%10**9
 return D[n]
while 1:print f(input()*2)