#include <cstdio>

using namespace std;

const int MOD = 666013;

long long a[5][5], r[5][5], aux[5][5];

int rasp(int n) {
    a[1][1] = a[2][2] = 1;
    r[1][1] = r[1][2] = r[2][1] = 1;

    for( ; n; n = n >> 1) {
        if(n & 1) {
            for(int i = 1; i <= 2; ++ i) {
                for(int j = 1; j <= 2; ++ j) {
                    aux[i][j] = 0;
                    for(int k = 1; k <= 2; ++ k) {
                        aux[i][j] = (aux[i][j] + ((r[i][k] * a[k][j]) % MOD)) % MOD;
                    }
                }
            }
            for(int i = 1; i <= 2; ++ i)
                for(int j = 1; j <= 2; ++ j)
                    a[i][j] = aux[i][j];
        }
        for(int i = 1; i <= 2; ++ i) {
            for(int j = 1; j <= 2; ++ j) {
                aux[i][j] = 0;
                for(int k = 1; k <= 2; ++ k) {
                    aux[i][j] = (aux[i][j] + ((r[i][k] * r[k][j]) % MOD)) % MOD;
                }
            }
        }
        for(int i = 1; i <= 2; ++ i)
            for(int j = 1; j <= 2; ++ j)
                r[i][j] = aux[i][j];
    }

    printf("%lld", a[1][2]);
}

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

    int n;
    scanf("%d", &n);

    rasp(n);

    return 0;
}