#include <iostream>
#include <fstream>

using namespace std;

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

#define mod 666013

void fura_valoarea(int A[2][2], int B[2][2])
{
    int i, j;
    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++)
            A[i][j] = B[i][j];
}

void inmultire_matrice(int A[2][2], int B[2][2], int rez[2][2])
{
    rez[0][0] = (A[0][0] * B[0][0] +  A[0][1] * B[1][0]) % mod;
    rez[0][1] = (A[0][0] * B[0][1] +  A[0][1] * B[1][1]) % mod;
    rez[1][0] = (A[1][0] * B[0][0] +  A[1][1] * B[1][0]) % mod;
    rez[1][1] = (A[1][0] * B[0][1] +  A[1][1] * B[1][1]) % mod;
}

void expo(int baza[2][2], int exp, int solutie[2][2])
{
    int acc[2][2] = {{1, 0}, {0, 1}}, aux[2][2] = {{1, 0}, {0, 1}};

    if(exp < 0)
        solutie[1][1] = 0;
    else if(exp == 0)
    {
        solutie[0][0] = 1;
        solutie[0][1] = 0;
        solutie[1][0] = 0;
        solutie[1][1] = 1;
    }
    else if(exp == 1)
        fura_valoarea(solutie, baza);
    else
    {
        fura_valoarea(acc, baza);
        for (int i = 1; i <= exp; i *= 2)
        {
            if ((i & exp))
            {
                inmultire_matrice(solutie, acc, aux);
                fura_valoarea(solutie, aux);
            }
            inmultire_matrice(acc, acc, aux);
            fura_valoarea(acc, aux);
        }
    }
}

int main()
{
    int Z[2][2], indice, Z_i[2][2] = {{1, 0}, {0, 1}}, M_i[1][2];
    Z[0][0] = 0; Z[0][1] = 1; Z[1][0] = 1; Z[1][1] = 1;

    fin>>indice;
    expo(Z, indice-1, Z_i);
    fout<<Z_i[1][1];
    return 0;
}