int f[12];m(i,j){bzero(f+8,16);for(j=8;j--;)f[8+j%4]=(f[8+j%4]+1ll*f[i+j/2]*f[4+j/4*2+j%2])%(int)1e9;bcopy(f+8,f+i,16);}main(i,n){for(;~scanf("%d",&n);printf("%d\n",f[0]),bzero(f,48))for(f[0]=f[3]=f[4]=f[5]=f[6]=i=1;i<=n;i<<=1)i&n&&m(0),m(4);}
Note that non-ascii characters in the above source code will be escaped (such as \x9f).