#include <bits/stdc++.h>
#define NM 5
#define M 666013
#define ull unsigned long long
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

ull n,z[NM][NM],m[NM][NM],aux[NM][NM];

void Solve();
void RidicLog(int);
void ProdusMat(int);

int main()
{   Solve();
    f.close();
    g.close();
    return 0;
}

void Solve()
{   f>>n;
    if(n<=1)
    {   g<<n;
        return;
    }
    z[1][2]=z[2][1]=z[2][2]=1;
    RidicLog(n-1);
    g<<m[2][2];
}

void RidicLog(int p)
{   if(p==1)
        m[1][2]=m[2][1]=m[2][2]=1;
    else
    {   int r=p%2;
        RidicLog(p/2);
        ProdusMat(r);
    }
}

void ProdusMat(int r)
{   for(int i=1; i<=2; i++)
        for(int j=1; j<=2; j++)
            aux[i][j]=m[i][j];
    aux[1][1]=(m[1][1]*m[1][1]%M+m[1][2]*m[2][1]%M)%M;
    aux[1][2]=(m[1][1]*m[1][2]%M+m[1][2]*m[2][2]%M)%M;
    aux[2][1]=(m[2][1]*m[1][1]%M+m[2][2]*m[2][1]%M)%M;
    aux[2][2]=(m[2][1]*m[1][2]%M+m[2][2]*m[2][2]%M)%M;
    if(r)
    {   m[1][1]=(aux[1][1]*z[1][1]%M+aux[1][2]*z[2][1]%M)%M;
        m[1][2]=(aux[1][1]*z[1][2]%M+aux[1][2]*z[2][2]%M)%M;
        m[2][1]=(aux[2][1]*z[1][1]%M+aux[2][2]*z[2][1]%M)%M;
        m[2][2]=(aux[2][1]*z[1][2]%M+aux[2][2]*z[2][2]%M)%M;
    }
    else
    {   m[1][1]=aux[1][1];
        m[1][2]=aux[1][2];
        m[2][1]=aux[2][1];
        m[2][2]=aux[2][2];
    }
}