#include <iostream>
#include <fstream>

using namespace std;

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

const int logk = 30;
const int MOD = 666013;
int dp[logk + 1][2][2];

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

void preprocess() {
    dp[0][0][0] = 0;
    dp[0][0][1] = 1;
    dp[0][1][0] = 1;
    dp[0][1][1] = 1;
    for (int i = 1; i <= logk; i++)
        mult(dp[i], dp[i-1], dp[i-1]);
}

void logp(int res[2][2], int k) {
    while (k > 0) {
        int msb = 31 - __builtin_clz(k);
        int aux[2][2] = {{0,0},{0,0}};
        mult(aux, res, dp[msb]);
        res[0][0] = aux[0][0];
        res[0][1] = aux[0][1];
        res[1][0] = aux[1][0];
        res[1][1] = aux[1][1];
        k -= (1<<msb);
    }
}

int main() {
    int k;
    fin >> k;
    if (k == 0)
        fout << 0;
    else if (k == 1)
        fout << 1;
    else if (k == 2)
        fout << 1;
    else {
        preprocess();
        int power[2][2] = {{0,1},{1,1}};
        logp(power, k-2);
        //mult(result, start, power);
        fout << power[1][1];

    }
  
    fout << '\n';

    return 0;
}