h={}
f=->n{h[n/=2]||=n<5?1:(eval'+f[n+1]*f[n+=2]'*2)%10**9}
loop{p f[eval(gets)*2+7]}