#include <bits/stdc++.h>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int mod=666013;
long long int k,z[2][2]={{0,1},{1,1}};
long long int mat[2][2]={{0,1},{1,1}},ans[2];
void multiplic(long long int t[2][2],long long int v[2][2])
{
    /// <=> t*=v;
    long long int rez[2][2],i,j;
    rez[0][0]=t[0][0]*v[0][0]+t[0][1]*v[1][0];
    rez[0][1]=t[0][0]*v[0][1]+t[0][1]*v[1][1];
    rez[1][0]=t[1][0]*v[0][0]+t[1][1]*v[0][1];
    rez[1][1]=t[1][0]*v[0][1]+t[1][1]*v[1][1];
    for(i=0;i<2;++i)
    {
        for(j=0;j<2;++j)
        {
            t[i][j]=(rez[i][j]+mod)%mod;
            //cout<<t[i][j]<<' ';
        }
        //cout<<'\n';
    }
    //cout<<"\n\n";
}
void calcul()
{
    ///mat = z ^ (k-1)
    ///baza = z;
    long long int pow=k-1;
    while(pow)
    {
        if(pow%2==1)
        {
            //cout<<'A'<<'\n';
            multiplic(mat,z);
        }
        //cout<<'B'<<'\n';
        multiplic(z,z);
        pow/=2;
    }
    ans[0]=mat[1][0];
    ans[1]=mat[0][1]+mat[1][1];
}
int main()
{
    fin>>k;
    calcul();
    fout<<ans[0]%mod;
    return 0;
}