#include <fstream>

using namespace std;

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

const int p = 666013;

long long k, a[3][3] = {{0, 0, 0}, {0, 0, 1}, {0, 1, 1}}, v[3][3] = {{0, 0, 0}, {0, 1, 0}, {0, 0, 1}}, c[3][3];

void copy(long long v1[3][3], long long v2[3][3], int n){
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            v1[i][j] = v2[i][j];
        }
    }
}

void inm(long long x[3][3], long long y[3][3], int n){
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            c[i][j] = 0;
            for (int k = 1; k <= n; ++k) {
                c[i][j] = (c[i][j] + x[i][k] * y[k][j]) % p;
            }
        }
    }
    copy(x, c, n);
}

int main(){
    fin >> k;
    k -= 2;
    while (k > 0) {
        if (k % 2) {
            inm(v, a, 2);
        }
        inm(a, a, 2);
        k /= 2;
    }
    fout << (v[2][1] + v[2][2]) % p;
    return 0;
}