//https://infoarena.ro/problema/kfib

#include <iostream>
#include <fstream>

using namespace std;

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

const int MOD = 666013;
int rez[2][2];

void inmultire(int a[2][2], int b[2][2])
{
    int c[2][2] = {0};

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

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

void power_of_manyyy(int mat[2][2], int p)
{
    rez[0][0] = rez[1][1] = 1;
    rez[1][0] = rez[0][1] = 0;

    while (p > 0)
    {
        if (p & 1)
            inmultire(rez, mat);

        inmultire(mat, mat);

        p >>= 1;
    }
}

int main()
{
    int k;
    int mat[2][2];

    fin >> k;

    mat[0][0] = 0;
    mat[1][0] = mat[0][1] = mat[1][1] = 1;

    power_of_manyyy(mat, k - 1);
    // rezultatul in rez

    fout << rez[1][1] << "\n";

    return 0;
}