#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

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

const int MOD = 666013;
int n;

void copy(int m[5][5], int v[5][5]) {
    for (int i = 1; i <= 2; ++i) {
        for (int j = 1; j <= 2; ++j) {
            m[i][j] = v[i][j];
        }
    }
}

void mult(int f[5][5], int v[5][5]) {
    int c[5][5];
    for (int i = 1; i <= 2; ++i) {
        for (int j = 1; j <= 2; ++j) {
            c[i][j] = 0;
        }
    }

    for (int i = 1; i <= 2; ++i) {
        for (int j = 1; j <= 2; ++j) {
            for (int k = 1; k <= 2; ++k) {
                c[i][j] = (c[i][j] + (long long)f[i][k] * v[k][j]) % MOD;
            }
        }
    }
    copy(f, c);
}


int main() {

    fin >> n;
    int p = n - 1;

    int m[5][5], s[5][5];;

    m[1][1] = 0;
    m[1][2] = 1;
    m[2][1] = 1;
    m[2][2] = 1;

    s[1][1] = 1;
    s[1][2] = 0;
    s[2][1] = 0;
    s[2][2] = 1;

    for (int k = 1; k <= p; k <<= 1) {
        if (k & p) {
            mult(s, m);
        }
        mult(m, m);

    }

    fout << s[2][2];

    fout.close();
    return 0;
}