#include <cstdio>
using namespace std;
const int MOD = 666013;
const int DIM = 5;
int a[DIM][DIM], b[DIM][DIM], ans[DIM][DIM];
void inmultire(int f1[][DIM], int f2[][DIM]){
    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;
}