#include <cstdio>

using namespace std;

const int MOD = 666013;
int a[5][5], ans[5][5], c[5][5];

void init() {
    ans[1][1] = 1;
    ans[2][2] = 1;

    a[1][1] = 1;
    a[1][2] = 1;
    a[2][1] = 1;
}

void mypow(int k) {
    for( ;k; k = k >> 1) {
        if(k & 1) {
            //ans = ans * a
            c[1][1] = ((long long)ans[1][1] * a[1][1] + (long long)ans[1][2] * a[2][1]) % MOD;
            c[1][2] = ((long long)ans[1][1] * a[1][2] + (long long)ans[1][2] * a[2][2]) % MOD;
            c[2][1] = ((long long)ans[2][1] * a[1][1] + (long long)ans[2][2] * a[2][1]) % MOD;
            c[2][2] = ((long long)ans[2][1] * a[1][2] + (long long)ans[2][2] * a[2][2]) % MOD;
            ans[1][1] = c[1][1];
            ans[1][2] = c[1][2];
            ans[2][1] = c[2][1];
            ans[2][2] = c[2][2];
        }
        //a = a * a
        c[1][1] = ((long long)a[1][1] * a[1][1] + (long long)a[1][2] * a[2][1]) % MOD;
        c[1][2] = ((long long)a[1][1] * a[1][2] + (long long)a[1][2] * a[2][2]) % MOD;
        c[2][1] = ((long long)a[2][1] * a[1][1] + (long long)a[2][2] * a[2][1]) % MOD;
        c[2][2] = ((long long)a[2][1] * a[1][2] + (long long)a[2][2] * a[2][2]) % MOD;
        a[1][1] = c[1][1];
        a[1][2] = c[1][2];
        a[2][1] = c[2][1];
        a[2][2] = c[2][2];
    }
    printf("%d", ans[1][2]);
}

int main() {
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    int k;
    scanf("%d", &k);
    init();
    mypow(k);

    return 0;
}