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

void matrix_mult(int (*A)[2], int (*B)[2])
{
    int C[2][2];
    memset(C, 0, sizeof(C));
    
    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;
    
    memcpy(A, C, sizeof(C));
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    int n, i;
    int T[2][2] = {{0, 1}, {1, 1}};
    int res[2][2] = {{1, 0}, {0, 1}};
    scanf("%d", &n);
    n -= 1;
    
    for (i=0; (1<<i)<=n; ++i) {
	if ((1<<i) & n)
	    matrix_mult(res, T);
	matrix_mult(T, T);
    }

    printf("%d\n", res[1][1]);
    return 0;
}