#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;

#ifdef HOME
const string inputFile = "input.txt";
const string outputFile = "output.txt";
#else
const string problemName = "kfib";
const string inputFile = problemName + ".in";
const string outputFile = problemName + ".out";
#endif

const int MOD = 666013;

int N;

struct matrix {
    int a, b, c, d;

    matrix() {
        a = d = 1;
        b = c = 0;
    }

    matrix(int _a, int _b, int _c, int _d) {
        a = _a;
        b = _b;
        c = _c;
        d = _d;
    }

    matrix operator*(matrix B) {
        int _a, _b, _c, _d;
        _a = (a * 1LL * B.a + b * 1LL * B.c) % MOD;
        _b = (a * 1LL * B.b + b * 1LL * B.d) % MOD;
        _c = (c * 1LL * B.a + d * 1LL * B.c) % MOD;
        _d = (c * 1LL * B.b + d * 1LL * B.d) % MOD;
        return matrix(_a, _b, _c, _d);
    }
};

matrix expLog(matrix B, int E) {
    matrix A;
    int i;

    for(i = E; i; i /= 2) {
        if(i & 1)
            A = A * B;
        B = B * B;
    }

    return A;
}

int main() {
    matrix B;

#ifndef ONLINE_JUDGE
    freopen(inputFile.c_str(), "r", stdin);
    freopen(outputFile.c_str(), "w", stdout);
#endif

    scanf("%d", &N);

    B = matrix(0, 1, 1, 1);
    B = expLog(B, N);

    printf("%d\n", B.c);

    return 0;
}