#include <fstream>
#define PRIM 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long v[2][2],prod[2][2],n;
void inmulteste(long long mat1[2][2],long long mat2[2][2])
{
    long long res[2][2];
    res[0][0]=mat1[0][0]*mat2[0][0]%PRIM+mat1[0][1]*mat2[1][0]%PRIM;
    res[0][0]%=PRIM;
    res[0][1]=mat1[0][0]*mat2[0][1]%PRIM+mat1[0][1]*mat2[1][1]%PRIM;
    res[0][1]%=PRIM;
    res[1][0]=mat1[1][0]*mat2[0][0]%PRIM+mat1[1][1]*mat2[1][0]%PRIM;
    res[1][0]%=PRIM;
    res[1][1]=mat1[1][0]*mat2[0][1]%PRIM+mat1[1][1]*mat2[1][1]%PRIM;
    res[1][1]%=PRIM;
    for(int i=0; i<2; ++i)
        for(int j=0; j<2; ++j)
            mat1[i][j]=res[i][j];
}
int main()
{
    f>>n;
    v[0][0]=0;
    v[0][1]=v[1][0]=v[1][1]=1;
    prod[0][0]=prod[1][1]=1;
    prod[0][1]=prod[1][0]=0;
    n--;
    for(int i=1; i<=n; i<<=1)
    {
        if(i&n) inmulteste(prod,v);
        inmulteste(v,v);
    }
    g<<prod[1][1]%PRIM<<'\n';
    return 0;
}