/* Al k-lea termen Fibonacci */

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define Mod 666013

int Z[2][2];
int s[2][2];

void inmultireMatrice(int a[2][2], int b[2][2]) {
	int c[2][2] = { {0, 0}, {0, 0} };
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % Mod;
	a[0][0] = c[0][0];
	a[0][1] = c[0][1];
	a[1][0] = c[1][0];
	a[1][1] = c[1][1];
}

void exp_mat(int n, int s[2][2], int Z[2][2]) {
	while (n > 0)
	{
		if (n % 2 == 1)
		{
			inmultireMatrice(s, Z);
		}
		inmultireMatrice(Z, Z);
		n /= 2;
	}
}

int main() {
	FILE *fin, *fout;
	int k;
	fin = fopen("kfib.in", "r");
	fout = fopen("kfib.out", "w");
	fscanf(fin, "%d", &k);
	Z[0][0] = 0;
	Z[0][1] = 1;
	Z[1][0] = 1;
	Z[1][1] = 1;
	s[0][0] = 1;
	s[0][1] = 0;
	s[1][0] = 0;
	s[1][1] = 1;
	exp_mat(k, s, Z);
	fprintf(fout, "%d", s[0][1]);
	fclose(fin);
	fclose(fout);
	getchar();
	return 0;
}