#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define FILES freopen("kfib.in" , "r" , stdin) , freopen("kfib.out" , "w" , stdout)
#define ll long long

using namespace std;

const ll N = 1e5 + 10;
const ll M = 666013;

ll n;
ll a[2][2] = { {0 , 1} , {1 , 1} } , b[2][2] = { {0 , 1} , {1 , 1} } , c[2][2];

int multiply(ll a[][2] , ll b[][2] , ll c[][2])
{
    int t , i , j;

    for(i = 0 ; i < 2 ; i++)
        for(j = 0 ; j < 2 ; j++)
            for(t = 0 , c[i][j] = 0 ; t < 2 ; t++)
                c[i][j] = (c[i][j] + a[i][t] * b[t][j]) % M;

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

void pw(int p)
{
    for( ; p ; p >>= 1 , multiply(a , a , c))
        if(p & 1)
            multiply(b , a , c);
}

signed main()
{
	#ifndef ONLINE_JUDGE
		FastIO , FILES;
	#endif

    cin >> n;
    pw(n - 1);
    cout << b[0][1];

    return 0;
}