#include<bits/stdc++.h>
#define in f
#define out g
using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");


long long k;
const int MOD = 666013;
long long M[2][2]= {0, 1, 1, 1};
long long S[2][2]= {1, 0, 0, 1};

int ori(long long S[2][2], long long M[2][2]) {

    long long d = (S[0][0] * M[0][0] + S[0][1] * M[1][0]) % MOD;
    long long a = (S[0][0] * M[0][1] + S[0][1] * M[1][1]) % MOD;
    long long n = (S[1][0] * M[0][0] + S[1][1] * M[1][0]) % MOD;
    long long i = (S[1][0] * M[0][1] + S[1][1] * M[1][1]) % MOD;
    S[0][0] = d;
    S[0][1] = a;
    S[1][0] = n;
    S[1][1] = i;
    //        m
    //        o
    //        c
    //        a
    //        n
    //        u -----------> POWER
}

int fib(long long k) {
    if(k == 1) {
        ori(S, M);
    } else {
        if(k % 2 == 1) {
            fib(k / 2);
            ori(S, S);
            ori(S, M);
        } else {
            fib(k / 2);
            ori(S, S);

        }
    }

}

int main() {

    in >> k;
    fib(k - 1);
    out << S[1][1];
}