#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define ll long long
#define ull unsigned long long
#define x first
#define y second
#define pi pair<int,int>
#define pl pair<ll,ll>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");


const ll N=1e4+5,INF=1e18,MOD=666013,M=1e2+5,inf=INT_MAX;

ll n;
ll a[2][2],init[2][2];

ll mult(ll a[2][2],ll b[2][2],ll c[2][2])
{
    ll aux[2][2];
    aux[0][0]=aux[1][0]=aux[1][1]=aux[0][1]=0;
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            for(int k=0;k<2;k++)
            {
                aux[i][j]+=a[i][k]*b[j][k]%MOD;
            }
        }
    }
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            a[i][j]=aux[i][j]%MOD;
        }
    }
}

ll logpow(ll a[2][2],ll n)
{
    while(n)
    {
        if(n%2==1)
        {
            mult(init,a,init);
        }
        mult(a,a,a);
        n/=2;
    }
}

int main()
{
    fin>>n;
    a[0][1]=a[1][0]=a[1][1]=1;
    init[0][1]=init[1][0]=init[1][1]=1;

    logpow(a,n-2);

    fout<<init[1][1];

}