#include <iostream>
#include <fstream>
#include <algorithm>

#define SIZE 4
#define HSIZE 2
#define MOD 666013

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

int **v, **z;

void matrix_multiplication(int** rez, int** a, int** b){
	for (int i = 0; i < HSIZE; i++){
		for (int j = 0; j < HSIZE; j++){
			for (int k = 0; k < HSIZE; k++){
				rez[i][j] += a[i][k] * b[k][j]; 
			}
		}
	}
}

void power_up(int** a, int k){

	/* Verificare cazuri de baza */
	if (k == 0){
		for (int i = 0; i < HSIZE; i++)
			for (int j = 0; j < HSIZE; j++)
				a[i][j] = 1;
		return;
	}
		
	if (k == 1){
		for (int i = 0; i < HSIZE; i++)
			for (int j = 0; j < HSIZE; j++)
				a[i][j] = v[i][j];
		return;
	}
		
	/* Alocare matrice intermediare. */
	int** a1 = (int**) calloc(sizeof(int), HSIZE);
	int** a2 = (int**) calloc(sizeof(int), HSIZE);
	for (int i = 0; i < HSIZE; i++){
		a1[i] = (int*) calloc(sizeof(int), HSIZE);
		a2[i] = (int*) calloc(sizeof(int), HSIZE);
	}
		
	power_up(a1, k / 2);
	power_up(a2, k - k / 2);
	matrix_multiplication(a, a1, a2);
}

int main()
{
	int n;
	
	/* Citire numar. */
	f >> n;

	/* Initializari pentru vectorii folositi. */
	z = (int**) calloc(sizeof(int), HSIZE);
	v = (int**) calloc(sizeof(int), HSIZE);
	for (int i = 0; i < HSIZE; i++){
		z[i] = (int*) calloc(sizeof(int), HSIZE);
		v[i] = (int*) calloc(sizeof(int), HSIZE);
	}
	v[0][0] = 0; v[0][1] = v[1][0] = v[1][1] = 1;
	
	/* Functia de ridicare la putere a unei matrici. */
	power_up(z, n);
	
	/* Aflare solutie. */
	g << (z[1][1] % MOD);
	
    return 0;
}