#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define MOD 666013
struct mat{
long long a0,a1,a2,a3;
friend mat operator *(const mat &a, const mat &b){
    mat c;
    c.a0 = (a.a0*b.a0+a.a1*b.a2)%MOD;
    c.a1 = (a.a0*b.a1+a.a1*b.a3)%MOD;
    c.a2 = (a.a2*b.a0+a.a3*b.a2)%MOD;
    c.a3 = (a.a2*b.a1+a.a3*b.a3)%MOD;
    return c;

}

};


mat exp_mat(mat a, int p){
    if(p == 0)
    return {1,0,0,1};
    if(p == 1)
        return a;
    mat ax = exp_mat(a, p/2);
    mat rez = ax*ax;
    if(p%2==1)
        rez = rez*a;
    return rez;

}
int main()
{
    int n;
    fin>>n;
    mat q = {0,1,1,1};
    mat r = exp_mat(q,n);
    fout << r.a2;
    return 0;
}