#include <iostream>
#include <fstream>

std::ifstream f("kfib.in");
std::ofstream g("kfib.out");

using namespace std;

unsigned long long matr[2][2], f1 = 0, f2 = 1, k;


void inmultireMatr()
{
    int newF1, newF2;
    newF1 = matr[0][0] * f1 + matr[1][0] * f2;
    newF2 = matr[0][1] * f1 + matr[1][1] * f2;

    f1 = newF1 % 666013;
    f2 = newF2 % 666013;
}

int main()
{
    matr[0][1] = matr[1][0] = matr[1][1] = 1;
    matr[0][0] = 0;

    f>>k;

    if(k == 1) g<<f1;
    if(k == 2) g<<f2;

    if(k > 2)
    {
        int i = 2;
        while(i <= k)
        {
            inmultireMatr();
            i++;
        }

        g<<f2;
    }

    return 0;
}