#include<fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

int a[4][4] , b1[4][4] , c[4][4], n, k;

void multiply(int a[][4] , int b[][4] , int c[][4], int n){
	int k , j, i;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++){
			c[i][j]=0;
			for(k=1;k<=n;k++)
				c[i][j]+=a[i][k]*b[k][j] % 666013;
		}
}

void func(int a[][4] , int b, int c[][4]){
	if(b==0) {
		c[1][1] = c[2][2] = 1;
		c[1][2] = c[2][1] = 0;
	}
	else {
		int aux[4][4];
		func(a, b/2, aux);
		//long long aux= func ( a ,b/2);
		if(b%2==0) {
			multiply(aux, aux, c, 2);
//			return (aux*aux)%1999999973;
		}
		else {
			multiply(aux, aux, b1, 2);
			multiply(b1, a, c, 2);
			//return ((aux*aux)%1999999973)*a%1999999973;
		}
	}
}


int main(){
		f>>k;
		a[1][1] = 0;
		a[1][2] = a[2][1] = a[2][2] = 1;
		func(a, k-1, c);
		g<<c[2][2];
	return 0; 
}