b,m=1e9,z;main(a,n){for(;z--%32||gets(n,b=1,a=b&&!printf("%u\n",b));a=atoi(n)>>z&1?a:b+m-(b=a))a=(1LL*b*b+1LL%(b=b*(2LL*a+b)%m)*a*a)%m;}