#include <stdio.h>

using namespace std;

#define ll long long unsigned
#define pb push_back
#define mp make_pair

const int MOD = 666013;
int Z[2][2];
int S[2][2];
int A[2][2];

void mult(int A[][2], int B[][2], int C[][2]){
    int i,j,k;
    for(i = 0;i < 2;i++){
        for(j = 0;j < 2;j++){
            for(k = 0;k < 2;k++){
                C[i][j] = (0LL+C[i][j]+1LL*A[i][k]*B[j][k])%MOD;
            }
        }
    }
}

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

int lgpow(int e){
    S[0][0] = S[1][1] = 1;
    while(e){
        if(e&1){
            mult(S, Z, A);
            copyAndClear(A, S);
        }
        mult(Z, Z, A);
        copyAndClear(A, Z);
        e >>= 1;
    }
    return S[1][1];
}

int main(){
    int n,i,j;
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    scanf("%d",&n);
    if(n <= 2){
        printf("%d",n);
        return 0;
    }
    Z[0][0] = 0;
    Z[1][0] = Z[0][1] = Z[1][1] = 1;
    printf("%d",lgpow(n-1));
    return 0;
}