#include <bits/stdc++.h>
#define ll long long
using namespace std;

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

const int mod = 666013;
int n;
ll mat[2][2] =
{
    {1, 1},
    {1, 0}
};

void inmultire(ll a[2][2], ll b[2][2])
{
    int i, j, k;
    ll c[2][2] = {{0, 0}, {0, 0}};
    for (i = 0; i <= 1; i++)
        for (j = 0; j <= 1; j++)
            for (k = 0; k <= 1; k++)
                (c[i][j] += a[i][k]*b[k][j])%=mod;
    for (i = 0; i <= 1; i++)
        for (j = 0; j <= 1; j++)
            a[i][j] = c[i][j];
}

void putere(ll q[2][2], int x)
{
    if (x == 0)
        return;
    putere(q, x/2);
    inmultire(q, q);
    if (x % 2)
        inmultire(q, mat);
}

int main()
{
    int n;
    fin >> n;
    ll F[2][2] = {{1, 0},{0, 1}};
    putere(F, n-1);
    fout << F[0][0];
    return 0;
}