#include <fstream>

using namespace std;

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

const int MOD = 666013;

int k;
long long fib[2][2], ans[2];

void multiply(long long mat1[][2], long long mat2[][2]) {
    long long rslt[2][2] = {0};
    for (int i = 0; i < 2; i++)
        for (int k = 0; k < 2; k++)
            for (int j = 0; j < 2; j++)
                rslt[i][j] += (mat1[i][k] % MOD * mat2[k][j] % MOD) % MOD;

    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            mat1[i][j] = rslt[i][j];
}

void expo(long long n) {
    long long p[2][2] = {0};
    p[0][0] = p[1][1] = 1; //initializare matricea I2
    while (n) {
        if (n % 2 == 1)
            multiply(p, fib);
        multiply(fib, fib);
        n /= 2;
    }
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            fib[i][j] = p[i][j];
}

int main() {
    fib[0][1] = fib[1][0] = fib[1][1] = 1; //initializare matrice fibonacci

    fin >> k;

    if (k == 0) {
        fout << 0;
        return 0;
    }

    expo(k-1);

    fout << fib[1][1];

//    fout << '\n';
//    for (int i = 0; i < 2; i++) {
//        for (int j = 0; j < 2; j++)
//            fout << fib[i][j] << ' ';
//        fout << '\n';
//    }

    return 0;
}