#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

const int MOD = 666013;

int sol[3][3];

inline void mult(int a[][3], int b[][3], int c[][3])
{
    for (int i = 1; i <= 2; ++i)
        for (int j = 1; j <= 2; ++j)
            for (int k = 1; k <= 2; ++k)
                c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % MOD;
}

inline void moveMatrix(int a[][3], int b[][3])
{
    for (int i = 1; i <= 2; ++i)
        for (int j = 1; j <= 2; ++j)
            a[i][j] = b[i][j];
}

inline void lgPow(int p, int m[][3])
{
    int c[3][3], aux[3][3];

    c[1][1] = 0;
    c[1][2] = 1;
    c[2][1] = 1;
    c[2][2] = 1;

    m[1][1] = m[2][2] = 1;

    while (p)
    {
        if (p & 1)
        {
            memset(aux, 0, sizeof(aux));
            mult(m, c, aux);
            moveMatrix(m, aux);
        }

        memset(aux, 0, sizeof(aux));
        mult(c, c, aux);
        moveMatrix(c, aux);
        p >>= 1;
    }
}

int n;

int main()
{
    fin >> n;

    lgPow(n - 1, sol);

    fout << sol[2][2] << '\n';

    return 0;
}