#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream f ("kfib.in");
ofstream t ("kfib.out");

const int mod=666013,dim=2;
int n;

struct matrix
{
    int v[dim][dim];
    matrix()
    {
        memset(v,0,sizeof(v));
    }
    void unit()
    {
        for(int i=0; i<dim; i++) v[i][i]=1;
    }
    matrix operator *(matrix a)
    {
        matrix rez;
        for (int i=0; i<dim; ++i)
            for (int j=0; j<dim; ++j)
                for (int y=0; y<dim; ++y)
                    rez.v[i][j]=(rez.v[i][j]+1LL*v[i][y]*a.v[y][j])%mod;
        return rez;
    }
};

matrix pow(matrix a,int power)
{
    matrix p;
    p.unit();
    for(int i=1; i<=power; i<<=1)
    {
        if(power&i) p=p*a;
        a=a*a;
    }
    return p;
}

int main()
{
    f>>n;
    matrix a;
    a.v[0][0]=0;
    a.v[1][0]=a.v[1][1]=a.v[0][1]=1;
    matrix rez=pow(a,n);
    t<<rez.v[1][0];
    return 0;
}