#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define fastIO ios_base::sync_with_stdio(NULL);cin.tie(NULL);
#define testCases int tc;cin>>tc;while(tc--);
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(),(a).end()
#define PI 3.1415926535897932384626433832795l
template<typename T> inline T gcd(T a,T b){return (b?__gcd(a,b):a);}
template<typename T> inline T lcm(T a,T b){return (a*(b/gcd(a,b)));}
const int NMAX = 1e5 + 5;
const int MOD = 666013;

ll res[2][2], mat[2][2];

static inline void solve();
static inline void multiply(ll a[][2], ll b[][2]);

int main(int argc, char** argv)
{

    (void)! freopen ("kfib.in", "r", stdin);
    (void)! freopen ("kfib.out", "w", stdout);
    fastIO

    // testCases
    solve();

    return 0;
}

static inline void solve()
{
    unsigned int k; cin >> k;
    res[0][1] = mat[0][1] = mat[1][0] = mat[1][1] = 1;

    if (k == 0) cout << 1;
    else if (k == 1) cout << 1;
    else if (k == 2) cout << 2;
    else 
    {
    	while (k)
    	{
        	if (k % 2 == 1)
            	multiply (res, mat);
        	multiply (mat, mat);
        	k /= 2;
    	}
    	cout << res[0][0];
    }
}

static inline void multiply(ll a[][2], ll b[][2])
{
	ll m[2][2];
	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] += 1LL * a[i][k] * b[k][j];
            m[i][j] %= MOD;
        }

    for (int i = 0; i < 2; ++i)
    	for (int j = 0; j < 2; ++j)
    		a[i][j] = m[i][j];
}