#include<fstream>
using namespace std;

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

#define M 666013

typedef struct matrix{
    long long a, b, c, d;
}Matrix;

Matrix factor(Matrix x, Matrix y)
{
    Matrix z;
    z.a = ( x.a * y.a % M + x.b * y.c % M ) % M;
    z.b = ( x.a * y.b % M + x.b * y.d % M ) % M;
    z.c = ( x.c * y.a % M + x.d * y.c % M ) % M;
    z.d = ( x.c * y.b % M + x.d * y.d % M ) % M;
    return z;
}

Matrix initMatrix(Matrix p, long long a, long long b, long long c, long long d)
{
    p.a = a;
    p.b = b;
    p.c = c;
    p.d = d;
    return p;
}

void printMatrix(Matrix p)
{
    out<<p.d<<'\n';
}

int main()
{


    Matrix p, m;
    p = initMatrix(p, 0, 1, 1, 1);
    m = initMatrix(m, 1, 0, 0, 1);

    int n;
    in >> n;
    n--;

    for( int i = 1; i<=n; i = (i<<1) )
    {
        if( i & n )
            m = factor(m, p);
        p = factor( p, p );
    }
    printMatrix(m);
    return 0;
}