#include <fstream>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

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

const int MOD = 666013;
int n;
int x[3][3], y[3][3];

void multiply(int a[3][3], int b[3][3]) {
    int r[3][3];
    for (int i = 1; i <= 2; ++i) {
        for (int j = 1; j <= 2; ++j) {
            r[i][j] = 0;
            for (int k = 1; k <= 2; ++k) {
                r[i][j] += ((long long)a[i][k] * b[k][j]) % MOD;
                r[i][j] %= MOD;
            }
        }
    }
    for (int i = 1; i <= 3; ++i) {
        for (int j = 1; j <= 3; ++j) {
            a[i][j] = r[i][j];
        }
    }
}

int main() {

    fin >> n;
    x[1][1] = x[2][2] = 1;
    y[1][2] = y[2][1] = y[2][2] = 1;
    n--;
    for (int i = 0; (1 << i) <= n; ++i) {
        if ((1 << i) & n) {
            multiply(x, y);
        }
        multiply(y, y);
    }
    fout << x[2][2];

    fout.close();
    return 0;
}