#include <bits/stdc++.h>
#define MOD 666013

using namespace std;

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

struct matrice
{
    long long m[2][2];
};

matrice ridicare_la_putere ( matrice A, int k );
matrice inmultire ( matrice A, matrice B );

int main()
{
    matrice A, B;
    int k;

    fin >> k;

    if ( k == 0 ) fout << 0;
    else if ( k == 1 || k == 2 ) fout << 1;
    else
    {
        A.m[0][0] = A.m[0][1] = A.m[1][0] = 1;
        A.m[1][1] = 0;

        B.m[0][0] = B.m[1][0] = 1;
        B.m[0][1] = B.m[1][1] = 0;

        A = ridicare_la_putere ( A, k - 2 );
        B = inmultire ( A, B );

        fout << B.m[0][0];
    }

    return 0;
}

matrice ridicare_la_putere ( matrice A, int k )
{
    if ( k == 1 ) return A;
    else if ( k % 2 == 0 ) return ridicare_la_putere ( inmultire ( A, A ), k / 2 );
    else return inmultire ( ridicare_la_putere ( inmultire ( A, A ), k / 2 ), A );
}

matrice inmultire ( matrice A, matrice B )
{
    matrice C;

    C.m[0][0] = ( A.m[0][0] * B.m[0][0] + A.m[0][1] * B.m[1][0] ) % MOD;
    C.m[0][1] = ( A.m[0][0] * B.m[0][1] + A.m[0][1] * B.m[1][1] ) % MOD;
    C.m[1][0] = ( A.m[1][0] * B.m[0][0] + A.m[1][1] * B.m[1][0] ) % MOD;
    C.m[1][1] = ( A.m[1][0] * B.m[0][1] + A.m[1][1] * B.m[1][1] ) % MOD;

    return C;
}