#include <fstream>
#define N 2
#define M 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

struct matrix{
    int m[N][N];
    matrix(){
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < N; ++j)
                m[i][j] = 0;
    }
    matrix operator*(const matrix& b){
        matrix c;
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < N; ++j)
                for(int k = 0; k < N; ++k)
                    c.m[i][j] = (c.m[i][j] + 1LL * m[i][k] * b.m[k][j]) % M;
        return c;
    }
};

matrix unit;
matrix putere(matrix x, int p){
    for(int i = 0; (1 << i) <= p; ++i){
        if(p & (1 << i))
            unit = unit * x;
        x = x * x;
    }
    return unit;
}

matrix a, b;
int main()
{
    unit.m[0][0] = 1;
    unit.m[1][1] = 1;

    a.m[0][0] = 1;
    a.m[0][1] = 1;

    b.m[0][1] = 1;
    b.m[1][0] = 1;
    b.m[1][1] = 1;

    int k;
    fin>>k;

    matrix c = putere(b, k);
    fout<<c.m[0][1];
    return 0;
}