# pragma GCC optimize("Ofast")
# pragma GCC target("avx,avx2,fma")
# pragma GCC optimization ("unroll-loops")
# include <bits/stdc++.h>
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
# define int ll
using namespace std;
int gcd(int a, int b)
{
    if(b) return gcd(b,a%b);
    return a;
}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<vector<int>>a(2,vector<int>(2,0)),f(2,vector<int>(2,0));
int k;
const int mod = 666013;


vector<vector<int>> prod(vector<vector<int>> a,vector<vector<int>> b)
{
	vector<vector<int>>prod(2,vector<int>(2,0));
	for(int i = 0;i < 2;i++)
	{
		for(int j = 0;j < 2;j++)
		{
			prod[i][j] = 0;
			for(int c = 0;c < 2;c++)
			{
				prod[i][j] += a[i][c] * b[c][j];
				prod[i][j] %= mod;
			}
		}
	}
	return prod;
}

int32_t main(){_
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
	cin >> k;
	f[0][0] = f[1][1] = 1;
	a[0][1] = a[1][1] = a[1][0] = 1;
	for(int i = 0;(1LL << i) <= k;i++)
	{
		if(k & (1LL << i))
		{
			f = prod(f,a);
		}
		a = prod(a,a);
	}
	rc(f[1][0]);
}