#include <bits/stdc++.h>
#define P 666013

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long n, f[4][4], v[4][4];
void Citire()
{
    fin >> n;
    n--;
}

void Inmultire(long long x[4][4], long long y[4][4])
{
    int c[4][4];
    c[1][1] = c[1][2] = c[2][1] = c[2][2] = 0;


    for(int i = 1; i <= 2; i++)
        for(int j = 1; j <= 2; j++)
        {
            long long s = 0;

            for(int k = 1; k <= 2; k++)
                s += (1LL * x[i][k] * y[k][j]);
            c[i][j] = s % P;
        }

    x[1][1] = c[1][1];
    x[1][2] = c[1][2];
    x[2][1] = c[2][1];
    x[2][2] = c[2][2];
}
void Rid()
{
    long long prod[4][4];
    prod[1][1] = prod[2][2] = 1;
    prod[1][2] = prod[2][1] = 0;

    while(n)
    {
        if(n % 2)
            Inmultire(prod, v);
        n /= 2;
        Inmultire(v, v);
    }

    v[1][1] = prod[1][1];
    v[1][2] = prod[1][2];
    v[2][1] = prod[2][1];
    v[2][2] = prod[2][2];
}
void Rezolvare()
{
    f[1][1] = 0;
    f[1][2] = 1;
    v[1][1] = 0;
    v[2][1] = v[2][2] = v[1][2] = 1;

    Rid();

    Inmultire(f, v);

    fout << 1LL * f[1][2] % P;
}
int main()
{
    Citire();
    Rezolvare();
    return 0;
}