//http://www.infoarena.ro/problema/kfib
#include <fstream>
#include <ostream>
#include <iostream>
#include <istream>
using namespace std;
#define ull unsigned long long int
const ull m = 666013;
ifstream in("kfib.in");
ofstream out("kfib.out");

struct Matrice
{
    ull a,b,c,d;
    Matrice(){};
    Matrice(ull a, ull b , ull c , ull d)
    {
        this->a = a;
        this->b = b;
        this->c = c;
        this->d = d;
    }
    Matrice operator *(const Matrice &other)
    {
        return Matrice( ((a*other.a)%m+(b*other.c)%m)%m, ((a*other.b)%m+(b*other.d)%m)%m,
                        ((c*other.a)%m+(d*other.c)%m)%m, ((c*other.b)%m+(d*other.d)%m)%m);
    }
} base,res,
     Z(0,1,
       1,1),
    I(1,0,
      1,0);//identitate
int main()
{

    ull k;
    in >> k;
    res = I;
    base = Z;
    while(k)
    {
        if(k&1)
            res = res * base;
        base = base * base;
        k >>= 1;
    }
    Matrice M1(0,1,
               0,0);
    res = M1 * res;//adica in res punem Mn = M1* Z^(i-1)
    out << res.b;
}