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

#define MOD 666013

using namespace std;

int k;

long long **Z;
long long **aux;

void initZ(){
    Z = new long long*[2];
    aux = new long long*[2];
    aux[0] = new long long[2];
    aux[1] = new long long[2];

    for (int i=0; i<2; i++){
        Z[i] = new long long[2];
    }
    Z[0][0] = 0;
    Z[0][1] = 1;
    Z[1][0] = 1;
    Z[1][1] = 1;
}

void init(long long **res){
    for (int i=0; i<2; i++){
        for (int j=0; j<2; j++){
            res[i][j] = 0;
        }
    }
}

long long **clone(long long **z){

    long long ** result = new long long *[2];
    result[0]  = new long long[2];
    result[1] = new long long[2];

    for (int i=0; i<2; i++){
        for (int j=0; j<2; j++){
            result[i][j] = z[i][j];
        }
    }

    return result;
}

void add(long long **result, long long **base){
    for (int i=0; i<2; i++){
        for (int j=0; j<2; j++){
            result[i][j] += base[i][j] % MOD;
            result[i][j] = result[i][j] % MOD;
        }
    }
}

void multiply(long long **baseZ, long long **another){
    init(aux);

    for (int i=0; i<2; i++){
        for (int j=0; j<2; j++){
            for (int k=0; k<2; k++){
                aux[i][j] += ((baseZ[i][k] % MOD) *(another[k][j]% MOD)) % MOD;
                aux[i][j] = aux[i][j] % MOD;
            }
        }
    }

    for (int i=0; i<2; i++){
        for (int j=0; j<2; j++){
            baseZ[i][j] = aux[i][j] % MOD;
        }
    }
}

long long **exponentiate(int exponent){

    long long **baseZ = clone(Z);
    long long **result;
    result = new long long*[2];
    result[0] = new long long[2];
    result[1] = new long long[2];

    init(result);
    result[0][0] = 1;
    result[1][1] = 1;

    while (exponent > 0){
        if (exponent % 2 == 1){
            multiply(result, baseZ);
            exponent--;
        }

        multiply(baseZ, baseZ);
        exponent = exponent/2;
    }

    return result;
}

long long fibo(int k){
    if (k == 1 || k == 2){
        return 1;
    }

    long long **ZP = exponentiate(k-2);

    return ((ZP[0][1] + ZP[1][1]) % MOD);
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    scanf("%d", &k);

    initZ();
    long long kthFibo = fibo(k);

    printf("%lld", kthFibo);
    return 0;
}