#include<bits/stdc++.h>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
const int MOD = 666013;
int K;
long long A1[2][2], A[2][2];

void Multiply(long long A[2][2], long long B[2][2]) {
    long long C1[2][2], C2[2][2];
    C1[0][0] = A[0][0];C1[0][1] = A[0][1];C1[1][0] = A[1][0];C1[1][1] = A[1][1];
    C2[0][0] = B[0][0];C2[0][1] = B[0][1];C2[1][0] = B[1][0];C2[1][1] = B[1][1];
    A[0][0] = (1LL * (C1[0][0] * C2[0][0] + C1[0][1] * C2[1][0])) % MOD;
    A[0][1] = (1LL * (C1[0][0] * C2[0][1] + C1[0][1] * C2[1][1])) % MOD;
    A[1][0] = (1LL * (C1[1][0] * C2[0][0] + C1[1][1] * C2[1][0])) % MOD;
    A[1][1] = (1LL * (C1[1][0] * C2[0][1] + C1[1][1] * C2[1][1])) % MOD;

}

void LogPow(int K) {
    long long R[2][2];
    R[0][0] = R[1][1] = 1;
    R[0][1] = R[1][0] = 0;
    while(K) {
        if(K % 2 == 1)
            Multiply(R,A);
        Multiply(A,A);
        K /= 2;
    }
    Multiply(A1,R);
    out << A1[0][0] << '\n';
}

int main() {
    in >> K;
    A1[0][0] = 1;A1[0][1] = 1;
    A[0][1] = 1;A[1][0] = 1;A[1][1] = 1;
    LogPow(K-1);

}