#include <fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define MOD 666013
typedef long long matrice[2][2];

matrice matr;

void prod(matrice, matrice, matrice) ;
void putere(int) ;
void cpy(matrice, matrice) ;

int main()
{
    int n;
    fin >> n;
    if(n < 2)
    {
        fout << n << '\n';
        return 0;
    }

    matr[0][1] = matr[1][0] = matr[1][1] = 1;
    putere(n);

    fout << matr[1][0] << '\n';
    return 0;
}


void prod(matrice a, matrice b, matrice c)
{
    c[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
    c[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
    c[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
    c[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];

    c[0][0] %= MOD; c[0][1] %= MOD; c[1][0] %= MOD; c[1][1] %= MOD;
}

void putere(int exp)
{
    matrice rez, temp;
    rez[0][0] = rez[1][1] = 1; rez[0][1] = rez[1][0] = 0;

    for(; exp; exp >>= 1)
    {
        if((exp & 1) == 1)
        {
            prod(rez, matr, temp);
            cpy(rez, temp);
        }

        prod(matr, matr, temp);
        cpy(matr, temp);
    }

    cpy(matr, rez);
}


void cpy(matrice a, matrice b)
{
    a[0][0] = b[0][0]; a[0][1] = b[0][1];
    a[1][0] = b[1][0]; a[1][1] = b[1][1];
}