#include <iostream>
#include <fstream>

using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
const int MOD = 666013;
struct mat{
    long long m[2][2];
};

mat produs(mat a, mat b) {
    mat x;
    x.m[0][0]= (a.m[0][0] * b.m[0][0] + a.m[0][1] * b.m[1][0])%MOD;
    x.m[0][1]= (a.m[0][0] * b.m[0][1] + a.m[0][1] * b.m[1][1])%MOD;
    x.m[1][0]= (a.m[1][0] * b.m[0][0] + a.m[1][1] * b.m[1][0])%MOD;
    x.m[1][1]= (a.m[1][0] * b.m[0][1] + a.m[1][1] * b.m[1][1])%MOD;
    return x;
}
mat putere( mat a, int n ){
    if( n == 1 )
        return a;
    if( n % 2 == 1 )
        return produs(a, putere( produs(a, a) , n/2 ));
    return putere( produs(a, a), n/2 );
}

int main()
{
    int n;
    in >> n;
    mat a,b;
    b.m[0][0]=0;
    b.m[0][1]=1;
    b.m[1][0]=1;
    b.m[1][1]=1;
    a.m[0][0]=0;
    a.m[0][1]=1;
    a.m[1][0]=1;
    a.m[1][1]=1;
    b = putere( b , n-2 );
    a = produs( a, b);
    out << a.m[1][1];
    return 0;
}