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

#define MODULO 666013

long long int **z;
long long int **id;
long long int *f;

long long int **multiply(long long int **first, long long int **second) {
    long long int **result;

    result = (long long int **)calloc(2, sizeof(long long int *));
    for (int i = 0; i < 2; i++)
        result[i] = (long long int *)calloc(2, sizeof(long long int));

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            long long int temp = 0;
            for (int k = 0; k < 2; k++) {
                temp += ((first[i][k] % MODULO) * (second[k][j] % MODULO)) % MODULO;
            }
            result[i][j] = temp % MODULO;
        }
    }

    return result;
}

long long int findNumber( long long int **matrix) {
    return (matrix[0][1] % MODULO + matrix[1][1] % MODULO) % MODULO;
}

long long int **p(long long int **x, int n)
{
    if ( n == 0 )
        return id;

    if ( n == 1 )
        return z;

    if(n%2==0) {
        long long int **k = p(x, n/2);
        return multiply(k, k);
    }

    return multiply(z, p(x,n-1));
}

void print(long long int **x) {
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            printf("%lld ", x[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int index;
    std::ifstream in("kfib.in");
    std::ofstream out("kfib.out");

    in >> index;

    z = (long long int **)calloc(2, sizeof(long long int *));
    for (int i = 0; i < 2; i++)
        z[i] = (long long int *)calloc(2, sizeof(long long int));

    z[0][0] = 0;
    z[0][1] = 1;
    z[1][0] = 1;
    z[1][1] = 1;

    id = (long long int **)calloc(2, sizeof(long long int *));
    for (int i = 0; i < 2; i++)
        id[i] = (long long int *)calloc(2, sizeof(long long int));

    id[0][0] = 1;
    id[0][1] = 0;
    id[1][0] = 0;
    id[1][1] = 1;

    f = (long long int *)calloc(2, sizeof(long long int));
    f[0] = 0;
    f[1] = 1;

    out << findNumber(p(z, index - 2));

    return 0;
}