#include <fstream>
#include <vector>

#define mod 666013

using namespace std;

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

int d, k;

struct matrice
{
    vector<vector<int> > v;

    matrice()
    {
        v.resize(d + 1,vector<int>(d + 1, 0));
    }
    void unitate()
    {
        for(int i = 1; i <= d; ++i)
        v[i][i] = 1;
    }
    matrice operator *(const matrice &meh) const
    {
        matrice r;
        for(int i = 1; i <= d; ++i)
            for(int j = 1; j <= d; ++j)
                for(int z = 1; z <= d; ++z)
                    r.v[i][j] = (r.v[i][j] + 1LL * v[i][k] * meh.v[k][j]) % mod;
        return r;
    }
}
matrice ridPutere(matrice a,int n)
{
    matrice p;
    p.unitate();
    for(int i = 1; i <= n;i<<=1)
    {
        if(n & i) p = p * a;
        a = a * a;
    }
    return p;
}

int main()
{
    in >> k;
    d = 2;
    matrice a;
    a.v[1][1] = 0;
    a.v[1][2] = a.v[2][2] = a.v[2][1] = 1;
    a = ridPutere(a, k - 1);
    out << a.v[2][2]);
}