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

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

using namespace std;

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

int v[3][3], z[3][3];
int n, i;

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

void power_up(int a[][3], int k) {
	int c[3][3], aux[3][3], i;

	memcpy(c, v, sizeof(v));
	a[0][0] = a[1][1] = 1;

	for (i = 0; (1 << i) <= k; i++) {
		if (k & (1 << i)) {
			memset(aux, 0, sizeof(aux));
			matrix_multiplication(a, c, aux);
			memcpy(a, aux, sizeof(aux));
		}

		memset(aux, 0, sizeof(aux));
		matrix_multiplication(c, c, aux);
		memcpy(c, aux, sizeof(c));
	}
}

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

	/* Initializari pentru vectorul folosit. */
	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 - 1);
	
	/* Scriere solutie. */
	g << z[1][1];
	
    return 0;
}