#include <cstdio>
using namespace std;
const int MOD = 666013;
const int NMAX = 5;
int a[NMAX][NMAX], b[NMAX][NMAX], ans[NMAX][NMAX];
void inmultire(int f1[][NMAX], int f2[][NMAX]){
    int i, j;
    ans[1][1] = (1LL * f1[1][1] * f2[1][1] + 1LL * f1[1][2] * f2[2][1]) % MOD;
    ans[2][1] = (1LL * f1[2][1] * f2[1][1] + 1LL * f1[2][2] * f2[2][1]) % MOD;
    ans[1][2] = (1LL * f1[1][1] * f2[1][2] + 1LL * f1[1][2] * f2[2][2]) % MOD;
    ans[2][2] = (1LL * f1[2][1] * f2[1][2] + 1LL * f1[2][2] * f2[2][2]) % MOD;
}
int my_pow(int k){
    for (; k; k >>= 1){
        if (k & 1){
            inmultire(a, b);
            a[1][1] = ans[1][1]; a[1][2] = ans[1][2];
            a[2][1] = ans[2][1]; a[2][2] = ans[2][2];
        }
        inmultire(b, b);
        b[1][1] = ans[1][1]; b[1][2] = ans[1][2];
        b[2][1] = ans[2][1]; b[2][2] = ans[2][2];
    }
    return a[2][2];
}
int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    int k;
    scanf("%d", &k);

    b[1][1] = 0;
    b[1][2] = b[2][1] = b[2][2] = 1;
    a[1][1] = a[2][2] = 1;
    printf("%d\n", my_pow(k - 1));
    return 0;
}