#include <fstream>

using namespace std;

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

long long n;
long long a[3][3],P[3][3],aux[3][3];

void produs(long long A[3][3], long long B[3][3], long long C[3][3], int t)
{
    for (int i=0; i<t; i++)
        for (int j=0; j<t; j++)
        {
            C[i][j] = 0;
            for (int l=0; l<t; l++)
            {
                C[i][j] += A[i][l]*B[l][j];
                C[i][j] %= 666013;
            }
        }
}

void atribuire(long long A[3][3], long long B[3][3], int t)
{
    for (int i=0; i<t; i++)
        for (int j=0; j<t; j++)
            A[i][j] = B[i][j];
}

int main()
{
    fin >> n;
    if (n == 0 || n == 1)
    {
        if (n == 0)
            fout << 0;
        else
            fout << 1;
        return 0;
    }
    n--;
    a[0][0] = 1; a[0][1] = 1; a[1][0] = 1;
    P[0][0] = 1; P[1][1] = 1;
    while (n >= 1)
    {
        if (n%2 == 1)
        {
            produs(a, P, aux, 2);
            atribuire(P, aux, 2);
        }
        produs(a, a, aux, 2);
        atribuire(a, aux, 2);
        n /= 2;
    }
    fout << P[0][0];
    return 0;
}