// Am zis eu ca fac o nebunie si stau si codez in noaptea
// de revelion, hau

#include <fstream>
#include <iostream>
#define mod 666013

using namespace std;

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

typedef struct {
    long long m[2][2];
} matrix;

matrix Z;

matrix multiply ( matrix x, matrix y ) {

    matrix res;
    res.m[0][0] = res.m[0][1] = res.m[1][0] = res.m[1][1] = 0;

    for ( int i = 0; i < 2; i++ ) {
        for ( int j = 0; j < 2; j++ ) {
            for (int k = 0; k < 2; k++) {
                res.m[i][j] += ( x.m[i][k] * y.m[k][j] );
                res.m[i][j] %= mod;
            }
        }
    }

    return res;
}

matrix lgput ( int pow ) {

    if ( pow == 1 )
        return Z;

    matrix temp = lgput ( pow/2 );
    matrix res = multiply ( temp, temp );
    if ( pow % 2 != 0 )
        res = multiply( res, Z );

    return res;
}

int main()
{
    int k;
    fin >> k;
    Z.m[0][0] = 0;
    Z.m[0][1] = Z.m[1][0] = Z.m[1][1] = 1;

    if ( k == 0 ) {
        fout << 0;
        return 0;
    } else if ( k == 1 ) {
        fout << 1;
        return 0;
    }

    matrix aux = lgput ( k-1 );
    matrix res;
    res.m[0][0] = res.m[1][0] = res.m[1][1] = 0;
    res.m[0][1] = 1;

    res = multiply( res, aux );
    fout << res.m[0][1] << "\n";

    return 0;
}