#include <fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

const long long MOD = 666013;

void multiply(const long long A[2][2], const long long B[2][2], long long C[2][2])
{
    C[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0])%MOD;
    C[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1])%MOD;
    C[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0])%MOD;
    C[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1])%MOD;
}

void raise(const long long A[2][2], const long long pow, long long P[2][2])
{
    if(pow == 0)
    {
        P[0][0] = 1;
        P[1][1] = 1;
        P[0][1] = 0;
        P[1][0] = 0;
    }
    else if(pow == 1)
    {
        P[0][0] = (A[0][0])%MOD;
        P[0][1] = (A[0][1])%MOD;
        P[1][0] = (A[1][0])%MOD;
        P[1][1] = (A[1][1])%MOD;
    }
    else
    {
        long long B[2][2];
        raise(A, pow/2, B);

        multiply(B,B,P);

        if(pow %2 ==1)
        {
            long long T[2][2];
            T[0][0] = P[0][0];
            T[0][1] = P[0][1];
            T[1][0] = P[1][0];
            T[1][1] = P[1][1];
            multiply(T,A,P);
        }
    }
}

int main()
{
    long long K;
    fin >> K;

    long long Z[2][2];
    Z[0][0] = 0;
    Z[0][1] = 1;
    Z[1][0] = 1;
    Z[1][1] = 1;
    long long P[2][2];

    raise(Z,K-1,P);
    fout<<P[1][1]<<'\n';

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