#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

const int MOD = 666013;
const int KMAX = 4;

// C = A * B
void multiply_matrix(int A[KMAX][KMAX], int B[KMAX][KMAX], int C[KMAX][KMAX]) {
    int tmp[KMAX][KMAX];

    for (int i = 0; i < KMAX; ++i) {
        for (int j = 0; j < KMAX; ++j) {

            unsigned 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));
}


// R = C^p
void power_matrix(int C[KMAX][KMAX], int p, int R[KMAX][KMAX]) {

    int tmp[KMAX][KMAX];

    // matrice identitate
    for (int i = 0; i < KMAX; ++i)
        for (int j = 0; j < KMAX; ++j)
            tmp[i][j] = (i == j);

    while (p != 1) {

        if (p % 2 == 0) {
            multiply_matrix(C, C, C);
            p /= 2;
        }
        else {
            multiply_matrix(tmp, C, tmp);
            p--;
        }
    }

    multiply_matrix(C, tmp, R);
}


// functia principala pentru garduri
int garduri_rapide(int n) {

    if (n <= 3) return 1;
    if (n == 4) return 2;

    int C[KMAX][KMAX] = {
        {0,0,0,1},
        {1,0,0,0},
        {0,1,0,0},
        {0,0,1,1}
    };

    power_matrix(C, n - 4, C);

    int sol = 1 * C[0][3] +
              1 * C[1][3] +
              1 * C[2][3] +
              2 * C[3][3];

    return sol % MOD;
}


int main() {

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

    int n;
    fin >> n;

    fout << garduri_rapide(n);

    return 0;
}