#include <cstdio>
#include <cstring>

using namespace std;

#define MAX_N 5
#define MOD 666013LL

long long Q[MAX_N][MAX_N];
long long R[MAX_N][MAX_N];
int k;

void mult (long long A[5][5], long long B[5][5]) {
     long long temp[MAX_N][MAX_N];
     
     memset (temp, 0, sizeof (temp));
     
     temp[1][1] = (A[1][1]*B[1][1] + A[1][2]*B[2][1]) % MOD;
     temp[1][2] = (A[1][1]*B[1][2] + A[1][2]*B[2][2]) % MOD;
     temp[2][1] = (A[2][1]*B[1][1] + A[2][2]*B[2][1]) % MOD;
     temp[2][2] = (A[2][1]*B[1][2] + A[2][2]*B[2][2]) % MOD;
     
     memcpy (A, temp, sizeof (temp));
}

int main () {
    freopen ("kfib.in", "r", stdin);
    freopen ("kfib.out", "w", stdout);
    
    scanf ("%d", &k);
    
    R[1][1] = R[2][2] = 1;
    Q[1][2] = Q[2][1] = Q[2][2] = 1;
    
    for (int i = 0; 1 << i <= k; ++i) {
        if ((1 << i) & k) mult (R, Q);       
        mult (Q, Q);
    }       
    printf ("%lld\n", R[2][1]);
    
    return 0;
}