#include <cstdio>
#include <cstring>
#define MOD 666013
#define MAX_N 2
#define MAX_M 3
#define MAX_P 3
using namespace std;

int mat[MAX_M][MAX_P];

void matrixMultiplication(int a[MAX_N][MAX_M], int b[MAX_M][MAX_P]){
    int c[MAX_N][MAX_P], i, j, k;
    for (i=0; i<MAX_N; i++)
        for (j=0; j<MAX_P; j++){
            c[i][j]=0;
            for (k=0; k<MAX_M; k++)
                c[i][j]=(c[i][j] + 1LL*a[i][k]*b[k][j]) % MOD;
        }
    memcpy(a, c, sizeof(c));
}

void lgput(int n){
    int ans[MAX_N][MAX_M];
    ans[0][0]=1;
    ans[0][1]=0;
    while (n){
        if (n&1)
            matrixMultiplication(ans, mat);
        matrixMultiplication(mat, mat);
        n=n>>1;
    }
    printf("%d\n", ans[0][0]);
}

int main(){
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    int K;
    scanf("%d", &K);

    mat[0][0]=1;
    mat[0][1]=1;
    mat[1][0]=1;
    mat[1][1]=0;

    lgput(K-1);

    return 0;
}