//#include <bits/stdc++.h>
#include <fstream>
#include <vector>
#include <bitset>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <math.h>
#include <iomanip>

using namespace std;
 
/********** TEMPLATE STARTS HERE ***********/
   
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define pb push_back
#define test int t; cin >> t; while(t--)
#define skip continue
#define stop break
#define sz(v) (int)v.size()
#define endl '\n'
#define PI 3.1415926535897932384626433832795
#define EPS 1e-9
#define gcd __gcd 
#define FO(i, a) for(auto & i : a)
#define debug(a) cout << #a << ": " << a << endl
#define debug1(a, l, r) FR(i, l, r) cout << a[i] << " "; cout << endl
#define SET(a, b) memset(a, b, sizeof(a));
#define refresh fflush(stdout);
#define digits(n) (int)(log10(n) + 1)
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <long long> vl;
typedef vector <pii> vii;
typedef vector <pll> vll;
   
const int INF = 0x3f3f3f3f;
const int LINF = 0x3f3f3f3f3f3f3f3f;
   
template <typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template <typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
  
/*********** TEMPLATE ENDS HERE *************/

ifstream cin("kfib.in");
ofstream cout("kfib.out");

const int MOD = 666013;

#define int long long

int mat[5][5];

void prod(int a[5][5], int b[5][5])
{
	int t[5][5];
	t[1][1] = (a[1][1] * b[1][1] + a[1][2] * b[2][1]) % MOD;
	t[1][2] = (a[1][1] * b[1][2] + a[1][2] * b[2][2]) % MOD;
	t[2][1] = (a[2][1] * b[1][1] + a[2][2] * b[2][1]) % MOD;
	t[2][2] = (a[2][1] * b[1][2] + a[2][2] * b[2][2]) % MOD;
	
	for(int i = 1; i <= 2; i++)
		for(int j = 1; j <= 2; j++)
			a[i][j] = t[i][j];
	
}

int v[5][5];

void lgput(int k)
{
	while(k > 0)
	{
		if(k & 1)
		{
			k--;
			prod(v, mat);
		}
		prod(mat, mat);
		k /= 2;
	}
}

main()
{
	mat[1][1] = 0;
	mat[1][2] = 1;
	mat[2][1] = 1;
	mat[2][2] = 1;
	
	v[1][1] = v[2][2] = 1;
	
	int k;
	cin >> k;
	
	if(k == 1)
		return cout << 1, 0;
	
	if(k == 2)
		return cout << 1, 0;
	
	k -= 2;
	
	lgput(k);
	
	cout << v[1][2] + v[2][2];
}