#define F 1ll*f(++n/2)
m=1e9;h[5686];i;f(n){h[i=n%5686]=h[i]|n<5?:(F*F+F*F)%m;}main(){for(;gets(h);printf("%d\n",f(atoi()+3)));}