#include <iostream>
#include <vector>
#include <fstream>

#define ll long long

using namespace std;

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

const int MOD = 666013;

int K;


struct matS
{
    ll m[2][2];
};

matS matmult( matS& M1, matS& M2 )
{
    matS Mr = { 0, 0, 0, 0 };
    for( int i = 0; i < 2; ++i )
        for( int j = 0; j < 2; ++j )
        {
            for( int t = 0; t < 2; ++t )
            {
                Mr.m[i][j] += M1.m[t][j] * M2.m[i][t];
                Mr.m[i][j] %= MOD;
            }
        }
    return Mr;
}

matS matpow( matS add, int pow )
{
    matS res = { 1, 0, 0, 1 };
    while( pow )
    {
        if( pow % 2 == 1 )
            res = matmult( res, add );
        pow /= 2;
        add = matmult( add, add );
    }

    return res;
}


int main()
{
    fin >> K;
    if( K == 0 )
    {
        fout << 0;
        return 0;
    }

    matS M = {1, 1, 1, 0};

    M = matpow( M, K );

    fout << M.m[0][1];

    return 0;
}