#include<fstream>
#include<string.h>
#define MOD 666013
using namespace std;

long long p[2][2], r[2][2], n, A[2][2];

void multiply(long long a[2][2], long long b[2][2], long long c[2][2]) {
	long long i, j, k;
	for (i=0;i<=1;i++)
		for (j=0;j<=1;j++) {
			c[i][j] = 0;
			for (k=0;k<=1;k++) {
				c[i][j] += ((a[i][k] * b[k][j]) % MOD);
				c[i][j] %= MOD;
			}
		}
}




int main()
{
	ifstream f("kfib.in");
	ofstream g("kfib.out");
	f>>n;
	
	n -= 2;
//	r = 1;
	r[0][0] = r[1][1] = 1;
	r[1][0] = r[0][1] = 0;
	
	p[0][0] = p[0][1] = p[1][0] = 1;
	p[1][1] = 0;
	
	while (n) {
		if (n%2 == 1) {
//			r = r * p % MOD;
			multiply(r, p, A);
			memcpy(r, A, sizeof(A));
		}
		multiply(p, p, A);
		memcpy(p, A, sizeof(A));
//		p = (p * p) % MOD;
		n/=2;
	}
	
	
	
	g<<(r[0][0] + r[0][1]) % MOD;
	return 0;
}