#include <fstream>
#include <iostream>

#define MOD 666013
#define KMAX 2

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

long long k;

void multiply_matrix(long long A[KMAX][KMAX], long long B[KMAX][KMAX], long long C[KMAX][KMAX]) {
    long long tmp[KMAX][KMAX];
    
    for (int i = 0; i < KMAX; i++) {
        for (int j = 0; j < KMAX; j++) {
            long long sum = 0;

            for (int k = 0; k < KMAX; k++) {
                sum += 1LL * A[i][k] * B[k][j];
            }
            tmp[i][j] = sum % MOD;
        }
    }

    memcpy(C, tmp, sizeof(tmp));
}

void power_matrix(long long C[KMAX][KMAX], long long p, long long R[KMAX][KMAX]) {
    long long tmp[KMAX][KMAX];

    for (int i = 0; i < KMAX; i++) {
        for (int j = 0; j < KMAX; j++) {
            tmp[i][j] = (i == j) ? 1 : 0;
        }
    }
    
    while (p != 1) {
        if (p % 2 == 0) {
            multiply_matrix(C, C, C);
            p = p / 2;
        }
        else {
            multiply_matrix(tmp, C, tmp);
            p--;
        }
    }

    multiply_matrix(C, tmp, R);
}

int main()
{
    f >> k;

    if (k == 1 || k == 2) {
        g << "1\n";
        return 0;
    }

    long long C[KMAX][KMAX] = { {0LL, 1LL}, {1LL, 1LL} };
    power_matrix(C, k - 2, C);

    long long sol = C[0][1] + C[1][1];
    g << sol % MOD << "\n";

    f.close();
    g.close();
    return 0;
}