#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;

struct Mat{
	long long m[2][2];
	Mat() {
		m[0][0] = 0;
		m[0][1] = m[1][0] = m[1][1] = 1;
	}
	Mat(Mat &a) {
		for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++) m[i][j] = a.m[i][j];
	}
	Mat& operator*=(Mat a) {
		Mat c(*this);
		for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++) {
			m[i][j] = 0;
			for (int k = 0; k < 2; k++) {
				m[i][j] = (m[i][j] + c.m[i][k] * a.m[k][j]) % 666013;
			}
		}
		return *this;
	}
	void print() {
		printf("%d\n", m[0][0]);
		//printf("%d %d\n", m[0][0], m[0][1]);
		//printf("%d %d\n", m[1][0], m[1][1]);
	}
} a, b;

void pow(int p) {
	if (p > 1) {
		pow(p/2);
		if (p%2) {
			a *= a;
			a *= b;
		} else {
			a *= a;
		}
	}	
}

int n;

int main() {
	
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	
	scanf("%d", &n);
	pow(n+1);
	a.print();
	
	return 0;
}