#include <fstream>

using namespace std;

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

const int MOD = 666013;

long long K, Z[3][3], Aux[3][3];

void Mult(long long A[3][3], long long B[3][3])
{
    long long C[3][3];

    for(int i = 1; i < 3; i++)
        for(int j = 1; j < 3; j++)
        {
            C[i][j] = 0;

            for(int k = 1; k < 3; k++)
                C[i][j] += A[i][k] * B[k][j];

            C[i][j] %= MOD;
        }

    for(int i = 1; i < 3; i++)
        for(int j = 1; j < 3; j++)
            A[i][j] = C[i][j];
}

int main()
{
    fin >> K;

    Aux[1][2] = Aux[2][1] = Aux[2][2] = Z[1][2] = 1;

    while(K)
    {
        if(K & 1) Mult(Z, Aux);

        Mult(Aux, Aux), K >>= 1;
    }
    fout << Z[1][1] << '\n';

    fin.close();
    fout.close();

    return 0;
}