#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <cstring>
#define MOD 666013

using namespace std;

FILE * f = fopen("kfib.in", "r");
FILE * g = fopen("kfib.out", "w");

long long mat[2][2] = {{0, 1}, {1, 1}}, mat1[2][2] = {{0, 1}, {1, 1}}, mat2[2][2];
int k;

void inmultire(long long a[2][2], long long b[2][2], long long c[2][2])
{
    long long aux[2][2];
    memset(aux, 0, sizeof(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] += (a[i][k] % MOD * b[k][j] % MOD) % MOD;
                aux[i][j] %= MOD;
            }
        }
    }
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            aux[i][j] %= MOD;
        }
    }
    memcpy(c, aux, sizeof(aux));
}

void lgput(int putere)
{
    if (putere == 1)
    {
        return;
    }
    lgput(putere / 2);
    inmultire(mat, mat, mat2);
    memcpy(mat, mat2, sizeof(mat2));
    memset(mat2, 0, sizeof(mat2));
    if (putere % 2 == 1)
    {
        inmultire(mat, mat1, mat2);
        memcpy(mat, mat2, sizeof(mat2));
        memset(mat2, 0, sizeof(mat2));
    }
    return;
}

int main()
{
    fscanf(f, "%i", &k);
    lgput(k - 1);
    fprintf(g, "%i", mat[1][1]);
    return 0;
}