#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,s,i;
int main()
{
    F>>n,e=h=v=w=z=1;
    for(i=0;(1<<i)<n;++i,p=A(u,u,v,w),q=A(u,v,v,z),r=A(w,u,z,w),s=A(w,v,z,z),u=p,v=q,w=r,z=s)
        if((n-1)&(1<<i))
            p=A(e,u,f,w),q=A(e,v,f,z),r=A(g,u,h,w),s=A(g,v,h,z),e=p,f=q,g=r,h=s;
    G<<h;
    return 0;
}