#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000000
#define rest 666013
FILE *fin = NULL;
FILE *fout = NULL;
#define LL long long int

LL A[2][2] = {{1, 0}, {0, 1}}, Z[2][2] = {{0, 1}, {1, 1}}, R[2][2] = {{1, 1}, {0, 0}};
LL N;

void Inmultire(LL A[][2], LL Z[][2])
{
    LL R[2][2];
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            R[i][j] = 0;
            for (int k = 0; k < 2; k++)
            {
                R[i][j] = (R[i][j] + A[i][k] * Z[k][j]) % rest;
            }
        }
    }
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            A[i][j] = R[i][j];
        }
    }
}

void putere_log(LL n)
{
    while (n > 0)
    {
        if (n % 2 == 0)
        {
            n = n / 2;
            Inmultire(Z, Z);
        }
        else
        {
            n--;
            Inmultire(A, Z);
        }
    }
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    scanf("%lld", &N);
    putere_log(N - 1);
    Inmultire(R, A);
    printf("%lld", R[0][0]);
    return 0;
}