#include <fstream>

using namespace std;

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

const int MOD = 666013;

void inmultire(long long A[3][3], long long B[3][3]){
        long long C[3][3];
        A[1][1] %= MOD;
        A[2][1] %= MOD;
        A[1][2] %= MOD;
        A[2][2] %= MOD;
        B[1][1] %= MOD;
        B[2][1] %= MOD;
        B[1][2] %= MOD;
        B[2][2] %= MOD;

        C[1][1] = (A[1][1] * B[1][1] % MOD + A[1][2] * B[2][1] % MOD) % MOD;
        C[1][2] = (A[1][1] * B[1][2] % MOD + A[1][2] * B[2][2] % MOD) % MOD;
        C[2][1] = (A[2][1] * B[1][1] % MOD + A[2][2] * B[2][1] % MOD) % MOD;
        C[2][2] = (A[2][1] * B[1][2] % MOD + A[2][2] * B[2][2] % MOD) % MOD;
        A[1][1] = C[1][1], A[1][2] = C[1][2], A[2][1] = C[2][1], A[2][2] = C[2][2];
}

void powlg(long long A[3][3], long long p){
        long long R[3][3];
        R[1][1] = 1, R[1][2] = 0, R[2][2] = 1, R[2][1] = 0;
        while(p > 0) {
                if(p & 1)
                        inmultire(R, A);
                inmultire(A, A);
                p >>= 1;
        }
        A[1][1] = R[1][1], A[1][2] = R[1][2], A[2][1] = R[2][1], A[2][2] = R[2][2];
}

long long n, A[3][3];

int main(){

        in >> n;
        A[1][1] = 0, A[1][2] = 1, A[2][1] = 1, A[2][2] = 1;
        powlg(A, n - 1);
        out << A[2][2];

        return 0;
}