#include <bits/stdc++.h>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
typedef long long ll;
ll k;
const ll mod=666013;
ll mat[3][3],c[3][3],rez[3][3],ans[3][3];
bool found=0;
void inmultire(ll a[3][3],ll b[3][3])
{
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
        {
            c[i][j]=0;
            for(int k=1;k<=2;k++)
            {
                ll val=(a[i][k]*b[k][j])%mod;
                c[i][j]=(c[i][j]+val)%mod;
            }
        }
}
void pwmat(ll b)
{
    while(b)
    {
        if(b&1)
        {
            if(!found)
            {
                found=1;
                for(int i=1;i<=2;i++)
                    for(int j=1;j<=2;j++)
                        rez[i][j]=mat[i][j];
            }
            else
            {
                inmultire(rez,mat);
                for(int i=1;i<=2;i++)
                    for(int j=1;j<=2;j++)
                        rez[i][j]=c[i][j];
            }
        }
        inmultire(mat,mat);
        for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
                mat[i][j]=c[i][j];
        b/=2;
    }
}
int main()
{
    fin>>k;
    if(k==0)
    {
        fout<<0;
        return 0;
    }
    if(k==1)
    {
        fout<<1;
        return 0;
    }
    mat[1][1]=0;
    mat[1][2]=1;
    mat[2][1]=1;
    mat[2][2]=1;
    pwmat(k-1);
    ans[1][1]=0;
    ans[1][2]=1;
    inmultire(ans,rez);
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            ans[i][j]=c[i][j];
    fout<<ans[1][2];
    return 0;
}