#include <iostream>
#include <fstream>
#define MOD 666013

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

void inmultire_mat(long long mat1[3][3],long long mat2[3][3]) {
    long long a = mat1[0][0];
    long long b = mat1[0][1];
    long long c = mat1[1][0];
    long long d = mat1[1][1];
    long long e = mat2[0][0];
    long long f = mat2[0][1];
    long long g = mat2[1][0];
    long long h = mat2[1][1];
    mat1[0][0] = a * e + b * g;
    mat1[0][1] = a * f + b * h;
    mat1[1][0] = c * e + d * g;
    mat1[1][1] = c * f + d * h;
    mat1[0][0] %= MOD;
    mat1[0][1] %= MOD;
    mat1[1][0] %= MOD;
    mat1[1][1] %= MOD;
}

void ridicare_log(int p) {
    long long sol[3][3];
    sol[0][0] = 1;
    sol[0][1] = 0;
    sol[1][0] = 0;
    sol[1][1] = 1;
    long long sol2[3][3];
    sol2[0][0] = 0;
    sol2[0][1] = 1;
    sol2[1][0] = 1;
    sol2[1][1] = 1;
    while (p) {
        if (p & 1) {
            inmultire_mat(sol,sol2);
            //cout << sol[0][0] << " " << sol[0][1] << '\n' << sol[1][0] << " " << sol[1][1] << "\n\n";
            p--;
        }
        else {
            //cout << sol2[0][0] << " " << sol2[0][1] << '\n' << sol2[1][0] << " " << sol2[1][1] << "\n\n";
            inmultire_mat(sol2, sol2);
            //cout << sol2[0][0] << " " << sol2[0][1] << '\n' << sol2[1][0] << " " << sol2[1][1] << "\n\n";
            p /= 2;
        }
    }
    fout << sol[0][1] + sol[1][1];
}

int main()
{
    int k;
    fin >> k;
    if (k == 1)
        fout << 1;
    if (k == 2)
        fout << 1;
    else
        ridicare_log(k-2);
}