#include<cstdio>
#include<algorithm>
#define matrix pair<pair<long long,long long>,pair<long long,long long> >
#define a11 first.first
#define a12 first.second
#define a21 second.first
#define a22 second.second
#define MOD 666013
using namespace std;
long long k;
matrix operator*(matrix,matrix);
matrix A,B;
matrix operator*(matrix U,matrix V)
{
    matrix R;
    R.a11=(U.a11*V.a11+U.a12*V.a21)%MOD;
    R.a12=(U.a11*V.a12+U.a12*V.a22)%MOD;
    R.a21=(U.a21*V.a11+U.a22*V.a21)%MOD;
    R.a22=(U.a21*V.a12+U.a22*V.a22)%MOD;
    return R;
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    A=make_pair(make_pair(0,1),make_pair(1,1));
    B=make_pair(make_pair(1,0),make_pair(0,1));
    scanf("%lld",&k);
    for(;k;k>>=1)
    {
       if(k & 1) B=B*A;
       A=A*A;
    }
    printf("%lld",B.a12);
    return 0;
}