#include <bits/stdc++.h>

#define MOD 666013
#define ll long long

int M[2][2];

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

int fib(ll n) {
    int T[2][2], S[2][2];
    S[0][0] = S[1][1] = 1;
    while(n) {
        if(n%2 == 1) {
            memset(T, 0, sizeof(T));
            mult_matrice(S, M, T);
            memcpy(S, T, sizeof(T));
        }
        memset(T, 0, sizeof(T));
        mult_matrice(M, M, T);
        memcpy(M, T, sizeof(T));
        n /= 2;
    }
    return S[0][1];
}



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

    M[0][0] = 0;
    M[0][1] = 1;
    M[1][0] = 1;
    M[1][1] = 1;

    scanf("%lld", &n);
    printf("%d", fib(n));
    


}