#include <cstdio>
#include <iostream>

#define PRIME 666013

void mulMat(int C[][2], int A[][2], int B[][2]) {
    int D[2][2];
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; ++ j) {
            D[i][j] = 0;
            for (int k = 0; k < 2; ++ k) {
                D[i][j] += ((long long)A[i][k] * B[k][j]) % PRIME;
            }
            D[i][j] %= PRIME;
        }
    }
    memcpy(C, D, 4 * sizeof(int));
}

int main () {
    freopen ("kfib.in", "r", stdin);
    freopen ("kfib.out", "w", stdout);
    
    int K;
    int A[2][2] = {{1, 1}, {1, 0}};
    int Fib[2][2] = {{1, 0}, {0, 1}};
    
    std::cin >> K;
    if (K < 2) {
        std::cout << K << "\n";
    }
    
    --K;
    for (int pow = 1; pow <= K; pow <<= 1) {
        if (K & pow) {
            mulMat(Fib, Fib, A);
        }
         mulMat(A, A, A);
    }    
    
    int res = Fib[0][0];
    std::cout << res << "\n"; 
    
    return 0;
}