#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int MOD = 666013;
using VI = vector<int>;
using Matrice = vector<VI>;
Matrice f1(1, VI(2, 1));
Matrice x(2, VI(2, 1));
Matrice r;
int k;

void Pow( Matrice& x, int p );
void Inmultire( Matrice a, Matrice b, Matrice& c );

int main()
{
    x[0][0] = 0;
    fin >> k;

    if ( k <= 2 )
    {
        if ( k == 0 )
            fout << 0 << '\n';
        else
            fout << 1 << '\n';

        fin.close();
        fout.close();
        return 0;
    }

    Pow(x, k - 2);
    Inmultire(f1, x, r);

    fout << r[0][1] << '\n';

    fin.close();
    fout.close();
    return 0;
}

void Pow( Matrice& x, int p )
{
    Matrice r(2, VI(2)); r[0][0] = 1, r[0][1] = 1;
    Matrice aux, aux1;
    while ( p > 0 )
    {
        if ( p & 1 )
        {
            Inmultire(r, x, aux);
            r = aux;
        }

        aux = x; aux1 = x;
        Inmultire(aux, aux1, x);
        p >>= 1;
    }

    x = r;
}

void Inmultire( Matrice a, Matrice b, Matrice& c )
{
    c = Matrice(a.size(), VI(b[0].size()));
    int i, j, k;
    for ( i = 0; i < a.size(); ++i )
        for ( j = 0; j < b.size(); ++j )
            for ( k = 0; k < a[0].size(); ++k )
                c[i][j] = ( 1LL*c[i][j] + 1LL*a[i][k]*b[k][j] ) % MOD;
}