#include <iostream>
#include <fstream>

using namespace std;

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

struct Matriks{
    typedef unsigned long long type;
    int w, h;
    type elems[5][5];
    Matriks(){}
    Matriks(int w, int h) : w(w), h(h)
    {
        for(int y = 0; y < h; y++){
            for(int x = 0; x < w; x++){
                elems[x][y] = 0;
            }
        }
    }
    void MakeIdentity()
    {
        if(w != h){
            cout << "wtf";
        }
        for(int i = 0; i < w; i++){
            elems[i][i] = 1;
        }
    }
    Matriks & operator*=(const Matriks & rhs)
    {
        Matriks tmp(rhs.w, h);
        if(rhs.h != w){
            cout << "wtf";
        }
        for(int i = 0; i < h; i++){
            for(int j = 0; j < rhs.w; j++){
                for(int k = 0; k < rhs.h; k++){
                    tmp.elems[j][i] += elems[k][i] * rhs.elems[j][k];
                }
            }
        }
        w = tmp.w, h = tmp.h;
        for(int y = 0; y < tmp.h; y++){
            for(int x = 0; x < tmp.w; x++){
                elems[x][y] = tmp.elems[x][y];
            }
        }
        return *this;
    }
    Matriks & operator %=(const type rhs)
    {
        for(int y = 0; y < h; y++){
            for(int x = 0; x < w; x++){
                elems[x][y] %= rhs;
            }
        }
        return *this;
    }
    void Bust()
    {
        for(int y = 0; y < h; y++){
            for(int x = 0; x < w; x++){
                cout << elems[x][y] << " ";
            }
            cout << "\n";
        }
    }
};

Matriks operator*(Matriks lhs, const Matriks & rhs)
{
    lhs *= rhs;
    return lhs;
}

Matriks a(2, 2), b(2, 1);
void CreateDaMatrices()
{
    a.elems[0][0] = 0;
    a.elems[1][0] = 1;
    a.elems[0][1] = 1;
    a.elems[1][1] = 1;
    
    b.elems[0][0] = 0;
    b.elems[1][0] = 1;
}

int mod = 666013;
Matriks Kapow(Matriks num, int exp)
{
    Matriks res(2, 2);
    res.MakeIdentity();
    for(int i = exp; i > 0; i >>= 1){
        if(i % 2 == 1){
            res *= num;
            res %= mod;
        }
        num *= num;
        num %= mod;
    }
    return res;
}

int main()
{
    int n;
    fin >> n;
    CreateDaMatrices();
    a = Kapow(a, n-1);
    b *= a;
    b %= mod;
    fout << b.elems[1][0];
    return 0;
}