#include <bits/stdc++.h>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
typedef long long ll;
const ll mod=666013;
ll power(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
ll ans[3][3],a[3][3],c[3][3];
void ans_a()
{
    for(ll i=1;i<=2;++i)
    for(ll j=1;j<=2;++j)
        c[i][j]=ans[i][j],
        ans[i][j]=0;
    for(ll k=1;k<=2;++k)
    for(ll i=1;i<=2;++i)
    for(ll j=1;j<=2;++j)
        ans[i][j]=(ans[i][j]+a[i][k]*c[k][j])%mod;
}
void a_a()
{
    for(ll i=1;i<=2;++i)
    for(ll j=1;j<=2;++j)
        c[i][j]=a[i][j],
        a[i][j]=0;
    for(ll k=1;k<=2;++k)
    for(ll i=1;i<=2;++i)
    for(ll j=1;j<=2;++j)
        a[i][j]=(a[i][j]+c[i][k]*c[k][j])%mod;
}
ll k;
int main()
{
    in>>k;
    if(k<=1)
    {
        out<<k<<'\n';
        return 0;
    }
    --k;
    ans[1][1]=ans[2][2]=1;
    a[1][2]=a[2][1]=a[2][2]=1;
    while(k)
    {
        if(k&1) ans_a();
        a_a();
        k>>=1;
    }
    out<<ans[2][2]%mod<<'\n';
    return 0;
}