#include <fstream>
#include <cstring>

using namespace std;

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

const int mod = 666013;

int mt[3][3], sol[3][3];

void init(){
    mt[0][0] = 0, mt[0][1] = 1;
    mt[1][0] = 1, mt[1][1] = 1;
}

void mult(int a[][3], int b[][3], int s[][3]){
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            for(int k = 0; k < 3; k++)
                s[i][j] = (s[i][j] + 1LL * a[i][k] * b[k][j]) % mod;
}

void solve(int p){
    int c[3][3], aux[3][3];

    memcpy(c, mt, sizeof(mt));
    sol[0][0] = sol[1][1] = 1;

    for(int i = 0; (1 << i) <= p; i++){
        memset(aux, 0, sizeof(aux));

        if(p & (1 << i)){
            mult(sol, c, aux);
            memcpy(sol, aux, sizeof(aux));
        }

        mult(c, c, aux);
        memcpy(c, aux, sizeof(c));
    }
}

int main()
{
    int n;
    cin >> n;
    init();
    solve(n - 1);
    cout << sol[1][1];

    return 0;
}