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