#include <iostream>
#include <fstream>
using namespace std;

#define MODUL0 666013

fstream f("kfib.in", ios::in), g("kfib.out", ios::out);
struct matr{
    long long l[2],c[2];
}p,x;

//long long p[2][2] = {{1,0},{0,1}};
//long long x[2][2] = {{0,1},{1,1}};

struct matr inmultirea_matricilor(matr a,matr b)
{
    matr t;
    t.l[0] = (a.l[0] * b.l[0] + a.l[1]* b.c[0])%MODUL0;
    t.l[1] = (a.l[0] * b.l[1] + a.l[1]* b.c[1])%MODUL0;
    t.c[0] = (a.c[0] * b.l[0] + a.c[1]* b.c[0])%MODUL0;
    t.c[1] = (a.c[0] * b.l[1] + a.c[1]* b.c[1])%MODUL0;
    return t;
}

void matrice (long long k)
{
    while(k)
    {
        if(k%2 ==1)
        {
            p = inmultirea_matricilor(p,x);
            --k;
        }
        else
        {
            x = inmultirea_matricilor(x,x);
            k /=2;
        }
    }
}

int main()
{
    p.l[0] = p.c[1] = x.l[1] = x.c[0] = x.c[1]= 1;
    p.l[1] = p.c[0] = x.l[0] = 0;
    int k;
    f>>k;
    matrice(k-1);
    g<<p.c[1];
}