#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int MOD = 666013;
int n;
struct mat22{
	long long int m00,m01,m10,m11;
};
struct mat21{
	long long int m00,m10;
};
mat22 produs2(mat22 a,mat22 b){
		mat22 c;
		c.m00 = ((a.m00*b.m00)%MOD + (a.m01*b.m10)%MOD)%MOD;
		c.m01 = ((a.m10*b.m00)%MOD + (a.m11*b.m10)%MOD)%MOD;
		c.m10 = ((a.m10*b.m00)%MOD + (a.m11*b.m10)%MOD)%MOD;
		c.m11 = ((a.m10*b.m01)%MOD + (a.m11*b.m11)%MOD)%MOD;
		return c;
};
mat21 produs1(mat22 a,mat21 b){
	 mat21 c;
	 c.m00 = ((a.m00*b.m00)%MOD + (a.m01*b.m10)%MOD)%MOD;
	 c.m10 = ((a.m10*b.m00)%MOD + (a.m11*b.m10)%MOD)%MOD;
	 return c;
};
mat22 fast_pow(mat22 a,int n){
	mat22 p = a;
	n--;
	while(n){
		if(n%2 == 1){
			p = produs2(p,a);
		};
		a = produs2(a,a);
		n/=2;
	};
	return p;
};
int fibbonaci(int n){
	mat22 fib1 = {1,1,1,0};
	mat21 fib2 = {1,1};
	mat21 ans = produs1(fast_pow(fib1,n-2),fib2);
	return ans.m00;
}
int main(){
	int n;fin >> n;
	fout << fibbonaci(n);
	return 0;
}