#include <fstream>
#include <iostream>

#define mod 666013
using namespace std;

uint64_t F[2][2] = {{1,1},{1,0}};
uint64_t unit[2][2] = {{1,1},{1,0}};

void inmultire(uint64_t A[2][2], uint64_t B[2][2])
{
    uint64_t x =  (1LL*A[0][0]*B[0][0] + 1LL*A[0][1]*B[1][0]) % mod;
    uint64_t y =  (1LL*A[0][0]*B[0][1] + 1LL*A[0][1]*B[1][1]) % mod;
    uint64_t z =  (1LL*A[1][0]*B[0][0] + 1LL*A[1][1]*B[1][0]) % mod;
    uint64_t w =  (1LL*A[1][0]*B[0][1] + 1LL*A[1][1]*B[1][1]) % mod;

    A[0][0] = x;
    A[0][1] = y;
    A[1][0] = z;
    A[1][1] = w;
}

void puterelog(int n)
{
    if(n == 0 || n == 1)
        return;

    if(!(n & 1))
        {

        puterelog(n/2);
        inmultire(F, F);
        }

    else
    {
        //memcpy(unit, F, 4*sizeof(uint64_t));

        puterelog(n/2);
        inmultire(F, F);
        inmultire(F, unit);
    }
}

int main()
{
    ifstream in ("kfib.in");
    ofstream out ("kfib.out");
    uint32_t k;
    in >> k;
    if(!k)
        {
        out<<"0";
        return 0;
        }

    puterelog(k - 1);

    /*for(int i = 0; i < 2; ++i)
    {
        for(int j = 0; j < 2; ++j)
            cout<<F[i][j]<<" ";
        cout<<endl;
    }*/

    //cout<<F[0][0];
    out<<F[0][0];
}