#include<fstream>
#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(std::ifstream("kfib.in")>>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),u=p,v=q,w=r)
        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 std::ofstream("kfib.out")<<h,0;
}