#include <bits/stdc++.h>
#define ll long long

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

int n;
const ll mod=666013;
pair<pair<ll,ll>,pair<ll,ll> > m;

pair<pair<ll,ll>,pair<ll,ll> > inm(pair<pair<ll,ll>,pair<ll,ll> > ma, pair<pair<ll,ll>,pair<ll,ll> > mb)
{
    ///a b    x y
    ///c d    z t
    ll a=ma.first.first;
    ll b=ma.first.second;
    ll c=ma.second.first;
    ll d=ma.second.second;

    ll x=mb.first.first;
    ll y=mb.first.second;
    ll z=mb.second.first;
    ll t=mb.second.second;
    return { {(a*x+b*z)%mod,(a*y+b*t)%mod},
            {(c*x+d*z)%mod,(c*y+d*t)%mod} };
}

pair<pair<ll,ll>,pair<ll,ll> > ridput(pair<pair<ll,ll>,pair<ll,ll> > mat, int put)
{
    if(put==0) return {{1,0}, {0,1}};
    if(put==1) return mat;
    if(put%2==0) return ridput(inm(mat,mat),put/2);
    if(put%2==1) return inm(mat,ridput(inm(mat,mat),put/2));
}

int main()
{
    fin>>n;
    m={{0,1},{1,1}};
    pair<pair<ll,ll>,pair<ll,ll> > res=ridput(m,n);
    fout<<res.second.first;
    return 0;
}