#include <fstream>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

long long o_mat[2][2], mat[2][2], mat2[2][2];
int i,j;

const int mod=666013;
void putere(long long mat[2][2], int p)
{
    if(p==1)
    {
        mat[0][0]=0;
        mat[0][1]=1;
        mat[1][0]=1;
        mat[1][1]=1;
        //cout<<p<<'\n'<<mat[0][0]<<' '<<mat[0][1]<<'\n'<<mat[1][0]<<' '<<mat[1][1]<<'\n';
        return;
    }
    if(p%2==0)
    {
        putere(mat, p/2);
        for(i=0; i<2; i++)
            for(j=0; j<2; j++)
                mat2[i][j]=mat[i][j];
        for(i=0; i<2; i++)
            for(j=0; j<2; j++)
                mat[i][j]=((mat2[i][0]*mat2[0][j])%mod+(mat2[i][1]*mat2[1][j])%mod)%mod;
        //cout<<p<<'\n'<<mat[0][0]<<' '<<mat[0][1]<<'\n'<<mat[1][0]<<' '<<mat[1][1]<<'\n';
    }
    if(p%2==1)
    {
        putere(mat, p-1);
        for(i=0; i<2; i++)
            for(j=0; j<2; j++)
                mat2[i][j]=mat[i][j];
        for(i=0; i<2; i++)
            for(j=0; j<2; j++)
                mat[i][j]=((o_mat[i][0]*mat2[0][j])%mod+(o_mat[i][1]*mat2[1][j])%mod)%mod;
        //cout<<p<<'\n'<<mat[0][0]<<' '<<mat[0][1]<<'\n'<<mat[1][0]<<' '<<mat[1][1]<<'\n';
    }
}
int main()
{
    int p;
    fin>>p;
    o_mat[0][0]=0;
    o_mat[0][1]=1;
    o_mat[1][0]=1;
    o_mat[1][1]=1;
    mat[0][0]=0;
    mat[0][1]=1;
    mat[1][0]=1;
    mat[1][1]=1;
    putere(mat, p+1);
    fout<<mat[0][0];
}