#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

typedef unsigned long long ulonglong;

class FibVector2
{
	public:
		FibVector2(ulonglong v0 = 0, ulonglong v1 = 1)
		{
			v[0] = v0;
			v[1] = v1;
		}
		
		ulonglong v[2];
};

class FibMatrix2
{
	public:
		FibMatrix2(unsigned long modulus = 666013)
			:	mod(modulus)
		{
			m[0][0] = 0;
			m[0][1] = 1;
			m[1][0] = 1;
			m[1][1] = 1;
		}
		
		void raiseToPower(unsigned long pow)
		{
			ulonglong r[2][2], t[2][2];
			r[0][0] = r[1][1] = 1;
			r[0][1] = r[1][0] = 0;
			
			for(unsigned int i = 0; i < pow; i++)
			{
				t[0][0] = r[0][0] * m[0][0] + r[0][1] * m[1][0];
				t[0][1] = r[0][0] * m[0][1] + r[0][1] * m[1][1];
				
				t[1][0] = r[1][0] * m[0][0] + r[1][1] * m[1][0];
				t[1][1] = r[1][0] * m[0][1] + r[1][1] * m[1][1];
				
				for(int i = 0; i < 2; i++)
					for(int j = 0; j < 2; j++)
						r[i][j] = t[i][j];
			}
			
			for(int i = 0; i < 2; i++)
				for(int j = 0; j < 2; j++)
				{
					m[i][j] = r[i][j];
				}
		}
		
		void raiseToPowerExp(unsigned long pow)
		{
			ulonglong r[2][2], t[2][2];
			r[0][0] = r[1][1] = 1;
			r[0][1] = r[1][0] = 0;
			
			while(pow != 0)
			{
				/**
				 *	Result = Result * X
				 */
				if(pow % 2 == 1)
				{
					t[0][0] = (((r[0][0] * m[0][0]) % mod) + ((r[0][1] * m[1][0]) % mod)) % mod;
					t[0][1] = (((r[0][0] * m[0][1]) % mod) + ((r[0][1] * m[1][1]) % mod)) % mod;
					
					t[1][0] = (((r[1][0] * m[0][0]) % mod) + ((r[1][1] * m[1][0]) % mod)) % mod;
					t[1][1] = (((r[1][0] * m[0][1]) % mod) + ((r[1][1] * m[1][1]) % mod)) % mod;
					
					for(int i = 0; i < 2; i++)
						for(int j = 0; j < 2; j++)
							r[i][j] = t[i][j];
				}
				
				/**
				 *	X = X^2
				 */
				t[0][0] = (((m[0][0] * m[0][0]) % mod) + ((m[0][1] * m[1][0]) % mod)) % mod;
				t[0][1] = (((m[0][0] * m[0][1]) % mod) + ((m[0][1] * m[1][1]) % mod)) % mod;
				
				t[1][0] = (((m[1][0] * m[0][0]) % mod) + ((m[1][1] * m[1][0]) % mod)) % mod;
				t[1][1] = (((m[1][0] * m[0][1]) % mod) + ((m[1][1] * m[1][1]) % mod)) % mod;
				
				for(int i = 0; i < 2; i++)
						for(int j = 0; j < 2; j++)
							m[i][j] = t[i][j];
				
				pow = pow / 2;
			}
			
			for(int i = 0; i < 2; i++)
				for(int j = 0; j < 2; j++)
				{
					m[i][j] = r[i][j];
				}
		}
		
		friend FibVector2 operator*(const FibVector2& fv, const FibMatrix2& fm)
		{
			return FibVector2(
				(((fv.v[0] * fm.m[0][0]) % fm.mod) + ((fv.v[1] * fm.m[1][0]) % fm.mod)) % fm.mod,
				(((fv.v[0] * fm.m[0][1]) % fm.mod) + ((fv.v[1] * fm.m[1][1]) % fm.mod)) % fm.mod);
		}
		
		ulonglong getNthFibonacci(unsigned long n)
		{
			if(n == 0)
			{
				return 0;
			}
			else
			{
				
				FibVector2 fv;
				
				raiseToPowerExp(n - 1);
				
				return (fv * (*this)).v[1];
			}
		}
		
	private:
		unsigned long mod;
		ulonglong m[2][2];
};

int main(int argc, char * argv[])
{
	ifstream fin("kfib.in");
	
	unsigned long n;
	fin >> n;
	
	fin.close();
	
	ofstream fout("kfib.out");
	
	FibMatrix2 fm;
	fout << fm.getNthFibonacci(n) << " ";
	
	fout.close();
	
	return 0;
}