#include <bits/stdc++.h>
#define SZ 2
#define MOD 666013

using namespace std;

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

int mat[SZ][SZ] = {
        {0, 1},
        {1, 1}
};

int n, sol[SZ][SZ];

void mult(int a[SZ][SZ], int b[SZ][SZ]) {
    int c[SZ][SZ];
    memset(c, 0, sizeof(c));
    for (int i = 0; i < SZ; i++)
        for (int j = 0; j < SZ; j++)
            for (int k = 0; k < SZ; k++)
                c[i][j] = (c[i][j] + (int) ((1LL * a[i][k] * b[k][j]) % MOD)) % MOD;
    memcpy(a, c, sizeof(c));
}

// more like sol * mat ^ n
void grrPow(int n) {
    while (n) {
        if (n % 2 == 1)
            mult(sol, mat);
        mult(mat, mat);
        n /= 2;
    }
}

int main() {
    fin >> n;
    sol[1][0] = 0;
    sol[1][1] = 1;
    grrPow(n - 1);
    fout << sol[1][1];
    return 0;
}