#include <bits/stdc++.h>

#define ll long long
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int MOD=666013;
ll a[3][3];
ll rez[3][3];
ll inm(ll a[][3], ll b[][3])
{
    ll c[3][3];
    for(ll i=1; i<=2; i++)
        for(ll j=1; j<=2; j++)
        {
            c[i][j]=(a[i][1]*b[1][j]%MOD + a[i][2]*b[2][j]%MOD)%MOD;
        }
    for(ll i=1; i<=2; i++)
        for(ll j=1; j<=2; j++)
            a[i][j]=c[i][j];
}

ll inm2(ll rez[][3])
{
    ll c[2][3];
    for(ll i=1; i<=2; i++)
    {
        c[1][i]=(0*rez[1][i]+1*rez[2][i])%MOD;
    }
    return c[1][1];
}
ll k;
int main()
{
    fin>>k;


    rez[1][1]=1;
    rez[2][2]=1;

    a[1][1]=0;
    a[1][2]=1;
    a[2][1]=1;
    a[2][2]=1;

    while(k)
    {
        if(k&1)
            inm(rez, a);
        k=k/2;
        inm(a,a);
    }

    fout<<inm2(rez);
    return 0;
}