# include <cstdio>
# include <string>

using namespace std;

# define FIN "kfib.in"
# define FOUT "kfib.out"
# define MOD 666013
# define MAX_K 3

long long rez;
int K, i, j, k, bit;
long long aux[MAX_K][MAX_K];
long long Sol[MAX_K][MAX_K];
long long Mat[MAX_K][MAX_K];

    int main() {
        freopen(FIN, "r", stdin);
        freopen(FOUT, "w", stdout);
        
        scanf("%d", &K);
        
        Sol[1][1] = Sol[2][2] = 1;
        Mat[1][2] = Mat[2][1] = Mat[2][2] = 1;
        
        int Bnd;
        for (Bnd = 0; (1 << Bnd) <= (K - 1) >> 1; ++Bnd);
        
        for (bit = 0; bit <= Bnd; ++bit) {
            if (((K - 1) & (1 << bit))) {
                memset(aux, 0, sizeof(aux));
                for (i = 1; i < MAX_K; ++i)
                   for (j = 1; j < MAX_K; ++j)
                      for (k = 1; k < MAX_K; ++k)
                         aux[i][j] = (aux[i][j] + Sol[i][k] * Mat[k][j]) % MOD;
                for (i = 1; i < MAX_K; ++i)
                   for (j = 1; j < MAX_K; ++j)
                      Sol[i][j] = aux[i][j];
            }
            
            memset(aux, 0, sizeof(aux));
            for (i = 1; i < MAX_K; ++i)
               for (j = 1; j < MAX_K; ++j)
                  for (k = 1; k < MAX_K; ++k)
                     aux[i][j] = (aux[i][j] + Mat[i][k] * Mat[k][j]) % MOD;
            for (i = 1; i < MAX_K; ++i)
               for (j = 1; j < MAX_K; ++j)
                  Mat[i][j] = aux[i][j];
        }
        
        K ? printf("%lld\n", Sol[2][2]) : printf("0\n");
        
        return 0;
    }