#include <fstream>
#include <cstring>

using namespace std;

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

const long long m = 666013;
long long k;

void matrixmult(long long a[2][2], long long b[2][2], long long c[2][2]) {
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++) {
            c[i][j] = 0;
            for (int k = 0; k < 2; k++)
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % m;
        }
}

int main() {
    long long matrix[2][2] = {0, 1, 1, 1}, sol[2][2] = {1, 0, 0, 1};
    fin >> k;
    for (long long i = 0; (1 << i) <= k; i++) {
        long long temp[2][2];
        if ((1 << i) & k) {
            matrixmult(matrix, sol, temp);
            memcpy(sol, temp, sizeof(sol));
        }
        memset(temp, 0, sizeof(temp));
        matrixmult(matrix, matrix, temp);
        memcpy(matrix, temp, sizeof(matrix));
    }
    fout << sol[0][1];
    return 0;
}