#include <iostream>
#include <fstream>
#define R 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
struct matrici{int a;int b;int c;int d;}Z,ans;
struct matric{int a;int b;}M;
matrici inm(matrici x,matrici y)
{
    matrici z;
    z.a=(x.a*y.a+x.b*y.c);
    z.b=(x.a*y.b+x.b*y.d);
    z.c=(x.c*y.a+x.d*y.c);
    z.d=(x.c*y.b+x.d*y.d);
    return z;
}
void putere(matrici x,int a)
{
    if(a==1)
    {
        ans=inm(ans,x);
        return;
    }
    if(a%2==1)
        ans=inm(ans,x);
    putere(inm(x,x),a/2);
}
int k;
int main()
{
    f>>k;
    if(k<3){g<<1;return 0;}
    //for(k=3;k<=10;k++)
    {
    ///ridicare matricea Z la putere k-1
    Z.a=0;
    Z.b=1;
    Z.c=1;
    Z.d=1;
    ans.a=1;
    ans.d=1;
    ans.b=ans.c=0;
    putere(Z,k-2);
    ///am de afisat M*ZZ
    g<<(ans.b+ans.d)%R<<'\n';
    }

}