#include <bits/stdc++.h>
 
#define scanf (void)!scanf

const int MOD = 666013;

using namespace std;

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

void MatProduct(int M[][2], int F[][2]) {
    int a = ((1LL * M[0][0] * F[0][0]) % MOD + (1LL * M[0][1] * F[1][0]) % MOD) % MOD;
    int b = ((1LL * M[0][0] * F[0][1]) % MOD + (1LL * M[0][1] * F[1][1]) % MOD) % MOD;
    int c = ((1LL * M[1][0] * F[0][0]) % MOD + (1LL * M[1][1] * F[1][0]) % MOD) % MOD;
    int d = ((1LL * M[1][0] * F[0][1]) % MOD + (1LL * M[1][1] * F[1][1]) % MOD) % MOD;

    M[0][0] = a, M[0][1] = b, M[1][0] = c, M[1][1] = d;
}

int binpow(int Mat[][2], int N) {
    int Res[2][2] = {{1, 0}, {0, 1}}; //Res = 1
    while(N) {
        if(N & 1) MatProduct(Res, Mat);
        MatProduct(Mat, Mat);
        N >>= 1;
    }
    return Res[0][0];
}

int KthFib(int N) {
    if(N == 0 || N == 1) 
        return 1;

    int Mat[2][2] = {{1, 1}, {1, 0}};
    return binpow(Mat, N - 1);
}

int main() {
    Open("kfib");

    int N;
    scanf("%d", &N);

    printf("%d", KthFib(N));
}