#include <bits/stdc++.h>
using namespace std;
const int K_MAX = 2;
const int MOD = 666013;
int N;



struct Matrice{
    int m[K_MAX][K_MAX];
    Matrice() {
        memset(m, 0, sizeof(m));
    }
};

Matrice inmultire(Matrice A, Matrice B) {
    Matrice rez;

    for(int i = 0; i < K_MAX; i++) {
        for(int j = 0; j < K_MAX; j++) {
            for(int k = 0; k < K_MAX; k++) {
                rez.m[i][j] += (1LL * A.m[i][k] * B.m[k][j]) % MOD;
            }
        }
    }

    return rez;
}

Matrice pw(Matrice A, int N) {
    if(N == 1) return A;

    if(N % 2 == 1) {
        return inmultire(A, pw(A, N - 1));
    }  
    else {
    Matrice P = pw(A, N / 2);
    return inmultire(P, P);
    }
}

int main() {
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    cin >> N;
    Matrice M;
    M.m[0][0] = 0, M.m[0][1] = M.m[1][0] = M.m[1][1] = 1;

    if(N == 0) cout << 1;
    else if(N == 1) cout << 1;
    else if(N == 2) cout << 2;
    else {
    M = pw(M, N - 2);
    cout << (M.m[1][0] + M.m[1][1]) % MOD;
    }
}