#include <stdio.h>
#include <stdlib.h>

#define MOD 666013

long long** I2;

long long** mult_mat(long long** A, long long** B) {
    
    long long** result;
    result = malloc(2*sizeof(long long*));
    result[0] = malloc(2*sizeof(long long));
    result[1] = malloc(2*sizeof(long long));
    result[0][0] = 0;
    result[0][1] = 0;
    result[1][0] = 0;
    result[1][1] = 0;

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                result[i][j] += (A[i][k] * B[k][j])%MOD;
            }
        }
    }
    return result;
}

long long** exp_log_rec(long long** M, unsigned p){
 //if(p < 0) return exp_log_rec(1 / n, -p);
 if(p == 0) return I2;
 if(p % 2 == 0) return (exp_log_rec(mult_mat(M,M), p/2));
 if(p % 2 == 1) return mult_mat(M , exp_log_rec(mult_mat(M,M), p/2));
 return M;
}

int main(){
    unsigned n=2;
    long long** Z;
    Z = malloc(2*sizeof(long long*));
    Z[0] = malloc(2*sizeof(long long));
    Z[1] = malloc(2*sizeof(long long));
    I2 = malloc(2*sizeof(long long*));
    I2[0] = malloc(2*sizeof(long long));
    I2[1] = malloc(2*sizeof(long long));
    Z[0][0] = 0;
    Z[0][1] = 1;
    Z[1][0] = 1;
    Z[1][1] = 1;
    I2[0][0] = 1;
    I2[0][1] = 0;
    I2[1][0] = 0;
    I2[1][1] = 1;

    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d" , &n);

    Z=exp_log_rec(Z,n-1);
    printf("%lld" , (Z[1][1])%MOD);

    return 0;
}