#include <bits/stdc++.h>
using namespace std;

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

#define ullong unsigned long long
#define aux 666013

class matrix
{
    ullong a[2][2];

public:
    matrix(){}
    matrix(ullong s, ullong b, ullong c, ullong d)
    {
        a[0][0]=s;
        a[0][1]=b;
        a[1][0]=c;
        a[1][1]=d;
    }
    pair<ullong, ullong> operator*(pair<ullong, ullong> p)
    {
        pair<ullong, ullong> r;
        r.first=(p.first*a[0][0]+p.second*a[1][0])%aux;
        r.second=(p.first*a[0][1]+p.second*a[1][1])%aux;
        return r;
    }
    matrix operator*(matrix m)
    {
        matrix r;
        r.a[0][0]=(a[0][0]*m.a[0][0]+a[0][1]*m.a[1][0])%aux;
        r.a[0][1]=(a[0][0]*m.a[0][1]+a[0][1]*m.a[1][1])%aux;
        r.a[1][0]=(a[1][0]*m.a[0][0]+a[1][1]*m.a[1][0])%aux;
        r.a[1][1]=(a[1][0]*m.a[0][1]+a[1][1]*m.a[1][1])%aux;
        return r;
    }
    void operator*=(matrix m)
    {
        (*this)=(*this)*m;
    }
};

matrix lgput(matrix m, ullong p)
{
    matrix res(1, 0, 0, 1);
    while(p)
    {
        if(p&1)
            res*=m;
        m*=m;
        p>>=1;
    }
    return res;
}

int main()
{
    ullong k;
    f>>k;
    pair<ullong, ullong> res=lgput(matrix(0, 1, 1, 1), k-1)*make_pair(1, 1);
    g<<res.first;
    f.close();
    g.close();
    return 0;
}