#include <fstream>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define p 666013
long long a[2][2],rez[2][2],aux[2][2];
int k;
void putere(int n)
{
    a[0][0]=0;
    a[0][1]=1;
    a[1][0]=1;
    a[1][1]=1;
    rez[0][0]=1;
    rez[1][1]=1;
    while(n)
    {


    if(n%2==1)
    {
        aux[0][0]=rez[0][0]*a[0][0]+rez[0][1]*a[1][0];
        aux[0][1]=rez[0][0]*a[0][1]+rez[0][1]*a[1][1];
        aux[1][0]=rez[1][0]*a[0][0]+rez[1][1]*a[1][0];
        aux[1][1]=rez[1][0]*a[0][1]+rez[1][1]*a[1][1];
        rez[0][0]=aux[0][0]%p;
        rez[0][1]=aux[0][1]%p;
        rez[1][0]=aux[1][0]%p;
        rez[1][1]=aux[1][1]%p;
    }
        aux[0][0]=a[0][0]*a[0][0]+a[0][1]*a[1][0];
        aux[0][1]=a[0][0]*a[0][1]+a[0][1]*a[1][1];
        aux[1][0]=a[1][0]*a[0][0]+a[1][1]*a[1][0];
        aux[1][1]=a[1][0]*a[0][1]+a[1][1]*a[1][1];
        a[0][0]=aux[0][0]%p;
        a[0][1]=aux[0][1]%p;
        a[1][0]=aux[1][0]%p;
        a[1][1]=aux[1][1]%p;
        n/=2;
    }

}
int main()
{
    fin>>k;
    if(k==0)
        fout<<0;
    else if(k<=2)
        fout<<1;
    else
    putere(k-1);
    fout<<rez[1][1];
    return 0;
}