#include <iostream>
#include <fstream>
#define R 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
struct matrici{long long a;long long b;long long c;long long d;}Z,ans;
matrici inm(matrici x,matrici y)
{
    matrici z;
    z.a=(x.a*y.a+x.b*y.c)%R;
    z.b=(x.a*y.b+x.b*y.d)%R;
    z.c=(x.c*y.a+x.d*y.c)%R;
    z.d=(x.c*y.b+x.d*y.d)%R;
    return z;
}
void putere(matrici x,int a)
{
    if(a==1)
    {
        ans=inm(ans,x);
        return;
    }
    if(a%2==1)
        ans=inm(ans,x);
    x=inm(x,x);
    a=a/2;
    putere(x,a);
}
long long int k;
int main()
{
    f>>k;
    if(k<3){g<<1;return 0;}
    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);
    g<<(ans.b+ans.d)%R<<'\n';
    //cout<<term1<<'\n'<<term2<<'\n'<<term3;
}