#include <iostream>
#include <fstream>


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

long long m[2][2], rasp[2][2], n;


void inmultirematrice(long long a[2][2], long long b[2][2])
{
    long long aa[2][2];
    aa[0][0] = a[0][0];
    aa[0][1] = a[0][1];
    aa[1][0] = a[1][0];
    aa[1][1] = a[1][1];

    long long bb[2][2];
    bb[0][0] = b[0][0];
    bb[0][1] = b[0][1];
    bb[1][0] = b[1][0];
    bb[1][1] = b[1][1];

    a[0][0] = (aa[0][0] * bb[0][0] + aa[0][1] * bb[1][0]) % 666013;
    a[0][1] = (aa[0][0] * bb[0][1] + aa[0][1] * bb[1][1]) % 666013;
    a[1][0] = (aa[1][0] * bb[0][0] + aa[1][1] * bb[1][0]) % 666013;
    a[1][1] = (aa[1][0] * bb[0][1] + aa[1][1] * bb[1][1]) % 666013;
}

void ridicare(long long n)
{
    while(n > 0)
    {
        if(n % 2 == 1)
            inmultirematrice(rasp, m);
        inmultirematrice(m, m);
        n /= 2;
    }
}

int main()
{

    fin >> n;


    m[0][0] = 1;
    m[0][1] = 1;
    m[1][0] = 1;
    m[1][1] = 0;


    rasp[0][0] = 1;
    rasp[0][1] = 0;
    rasp[1][0] = 0;
    rasp[1][1] = 1;


    ridicare(n);


    fout << rasp[0][1];
    return 0;
}