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