#include <fstream>
using namespace std;
ifstream  fin("kfib.in");
ofstream fout("kfib.out");
long long N,Z[3][3];
const long long MOD=666013;

void inmultire_matrice(long long a[][3], long long b[][3])
{
    long long c[3][3];

    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=2; j++)
        {
            c[i][j]=0;
            for(int k=1; k<=2; k++)
            {
                c[i][j]=(c[i][j]+(a[i][k]*b[k][j])%MOD)%MOD;
            }
        }
    }

    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=2; j++)
        {
            a[i][j]=c[i][j];
        }
    }
}

void fast_exp(long long baza[][3], long long exp)
{
    while(exp>0)
    {
        if(exp%2==1)
        {
            inmultire_matrice(Z,baza);
        }

        inmultire_matrice(baza,baza);
        exp=exp/2;
    }
}

int main()
{
    fin>>N;

    if(N==0)
    {
        fout<< 0 << "\n";
    }

    if(N==1)
    {
        fout<< 1 << "\n";
    }

    Z[1][1]=0;
    Z[1][2]=Z[2][1]=Z[2][2]=1;
    fast_exp(Z,N-1);

    /*
    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=2; j++)
        {
            fout<< Z[i][j] << " ";
        }
        fout<< "\n";
    }
    */
    fout<< Z[2][1] << "\n";
    return 0;
}