#include <stdio.h>
#define MOD 666013
long long a[2][2][2];
int x[2][2];
int prev = 1, curent = 0;
void produs(int i1, int i2, int i3){
	long long A[2][2]={{0}};
	if(i3 != -1)
		for(int i = 0 ; i < 2; ++i)
			for(int j = 0; j < 2; ++j)
				for(int k = 0; k < 2; ++k)
					A[i][j] =(A[i][j] + ((long long)a[i2][i][k] * a[i3][k][j])%MOD)% MOD;
	else
		for(int i = 0 ; i < 2; ++i)
			for(int j = 0; j < 2; ++j)
				for(int k = 0; k < 2; ++k)
					A[i][j] =(A[i][j] + ((long long)a[i2][i][k] * x[k][j])%MOD)% MOD;
				
	for(int i = 0; i < 2; ++i)
		for(int j = 0; j < 2; ++j)
			a[i1][i][j] = A[i][j];
}
void exp(int p){
	if(p == 1 )
		return;
	exp(p/2);
	prev ^= 1;
	curent ^= 1;
	produs(curent,prev,prev);
	if(p & 1)
		produs(curent,curent,-1);
}
int main(){
	int n;
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);
	scanf("%d", &n);
	n--;
	a[0][1][0] = 1;
	a[0][0][1] = 1;
	a[0][1][1] = 1;
	x[1][0] = 1;
	x[0][1] = 1;
	x[1][1] = 1;
	exp(n-1);
	printf("%d\n", (a[curent][0][1] + a[curent][1][1]) %MOD);
	return 0;
}