#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <list>
#include <string>
#include <algorithm>
using namespace std;
ifstream ff("kfib.in");
ofstream gg("kfib.out");
#define md 666013

struct mat{ 
	long long x0,x1,x2,x3; 
	mat(){ x0=0; x1=x2=x3=1; }
	mat& operator*=(const mat& a){
		int y0=(x0*a.x0+x1*a.x2)%md;
		int y1=(x0*a.x1+x1*a.x3)%md;
		int y2=(x2*a.x0+x3*a.x2)%md;
		int y3=(x2*a.x1+x3*a.x3)%md;
		x0=y0;x1=y1;x2=y2;x3=y3;
		return *this; }
	operator int(){ return int(x0); }
}r,a;
int k;

int exp(int p){
	while(p){
		if(p&1){ r*=a; p--; } else {
			a*=a; p>>=1; }
	}
	return r;
}

int main(){
	ff >> k;
	gg << exp(k) << "\n";
	return 0;
}