#include <stdio.h>
#include <string.h>
#define MOD 666013

int Z[3][3];
int Sol[3][3];
int N;

void _read() {
    freopen("kfib.in","r",stdin);
    freopen("kfib.out", "w", stdout);
    
    scanf("%d", &N);
}

void _multiply(int A[][3], int B[][3], int C[][3]) {
    
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            for(int k = 0; k < 2; ++k)
                C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % MOD;
}

void _logarithmicPower(int exp, int Sol[][3]) {
    
    int C[3][3];
    int AUX[3][3];
    Sol[0][1] = Sol[1][0] = Sol[1][1] = 1;
    
    memcpy(C, Z, sizeof(Z));
    
    for(int i = 0; (1<<i) <= exp; ++i) {
        if(exp & (1<<i)) {
            memset(AUX, 0, sizeof(AUX));
            _multiply(Sol, C, AUX);
            memcpy(Sol, AUX, sizeof(AUX));
        }
        
        memset(AUX, 0 , sizeof(AUX));
        _multiply(C, C, AUX);
        memcpy(C, AUX, sizeof(AUX));
    }
}

int main(void) {
   
    _read();
    
    Z[0][0] = 0;
    Z[0][1] = Z[1][0] = Z[1][1] = 1;
    
    _logarithmicPower(N - 1, Sol);
    
    printf("%d", Sol[0][1]);
    return 0;
}