#include <fstream>

using namespace std;

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

const int MOD = 666013;
int k;

void inmultireMat(int a[2][2], int b[2][2]) {
    int rez[2][2];
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            rez[i][j] = (1LL * a[i][0] * b[0][j] + 1LL * a[i][1] * b[1][j]) % MOD;
        }
    }
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            a[i][j] = rez[i][j];
        }
    }
}

int sol[2][2] = {
    {1, 0},
    {0, 1},
};

int aux[2][2] = {
    {0, 1},
    {1, 1},
};

int main() {
    fin >> k;
    while(k > 0) {
        if(k % 2 != 0) {
            inmultireMat(sol, aux);
        }
        inmultireMat(aux, aux);
        k /= 2;
    }
    fout << sol[0][1];
    return 0;
}