#include<bits/stdc++.h>
#define MOD 666013

using namespace std;

void inmultire_matrice(uint64_t A[2][2], uint64_t B[2][2],  uint64_t REZ[2][2]){
    REZ[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD;
    REZ[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD;
    REZ[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD;
    REZ[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD;
}

void copiaza (uint64_t A[2][2], uint64_t B[2][2]){
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            A[i][j] = B[i][j];
}

void lgput(uint64_t M[2][2], uint64_t p){
    uint64_t REZ[2][2] = {{1, 0}, {0, 1}}, TEMP[2][2];
    
    while (p > 0){
        if (p & 1){
            inmultire_matrice(REZ, M, TEMP);
            copiaza(REZ, TEMP);
        }

        inmultire_matrice(M, M, TEMP);
        copiaza(M, TEMP);

        p >>= 1;
    }
    
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            M[i][j] = REZ[i][j];
}

int main(){
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    uint64_t n , Z[2][2] = {{0, 1}, {1, 1}}, M1[2] = {0, 1};
    cin >> n;
    lgput(Z, n - 1);
    cout << (M1[0] * Z[0][1] + M1[1] * Z[1][1]) % MOD << '\n';
    return 0;
}