#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");

long long **v, **z;
long long i, j, k;

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

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

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

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

	/* Initializari pentru vectorii folositi. */
	z = (long long**) calloc(sizeof(long long), HSIZE);
	v = (long long**) calloc(sizeof(long long), HSIZE);
	for (i = 0; i < HSIZE; i++){
		z[i] = (long long*) calloc(sizeof(long long), HSIZE);
		v[i] = (long long*) calloc(sizeof(long long), 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;
}