#include <bits/stdc++.h>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int mod = 666013;
int a[3][3], b[3][3], v[3][3];
void copiere(int x[3][3], int y[3][3])
{
    for(int i = 1; i <= 2; ++i)
        for(int j = 1; j <= 2; ++j)
            x[i][j] = y[i][j];
}
void reset(int x[3][3])
{
    for(int i = 1; i <= 2; ++i)
        for(int j = 1; j <= 2; ++j)
            x[i][j] = 0;
}
void inmultire(int x[3][3], int y[3][3])
{
    int c[3][3];
    long long s = 0;
    for(int i = 1; i <= 2; ++i)
        for(int j = 1; j <= 2; ++j)
        {
            s = 0;
            for(int k = 1; k <= 2; ++k)
                s += (1LL*x[i][k]*y[k][j]);
            c[i][j] = s % mod;
        }
    copiere(x, c);
}
void lg(int k)
{
    v[1][1] = v[2][2] = 1;
    while(k)
    {
        if(k & 1)
        {
            k--;
            inmultire(v, b);
        }
        k /= 2;
        inmultire(b, b);
    }
}
int main()
{
    int k;
    fin >> k;
    if(k == 0)
        fout << 0;
    else if(k <= 2)
        fout << 1;
    else
    {
        a[1][2] = 1;
        b[1][2] = b[2][1] = b[2][2] = 1;
        lg(k - 1);
        inmultire(a, v);
        fout << a[1][2];
    }
    return 0;
}