#include<fstream>
using namespace std;
ifstream F("kfib.in");
ofstream G("kfib.out");
#define N 666013
#define A(a,b,c,d) (((1LL*a*b)%N+(1LL*c*d)%N)%N)
int n,e,f,g,h,u,v,w,z,p,q,r,i;
int main()
{
    for(F>>n,e=h=v=w=z=1,--n;n;n>>=1,p=A(u,u,v,w),q=A(u,v,v,z),r=A(w,u,z,w),z=A(w,v,z,z))
        if(n&1)
            p=A(e,u,f,w),q=A(e,v,f,z),r=A(g,u,h,w),h=A(g,v,h,z),e=p,f=q,g=r;
    return G<<h,0;
}