#include <cstdio>
#include <cstring>
#define MOD 666013
using namespace std;
long long k,p11,p12,p22,Sol[3][3],A[3][3];

void prod2()
{
    p11=(A[1][1]*A[1][1]+A[1][2]*A[2][1])%MOD;
    p12=(A[1][1]*A[1][2]+A[1][2]*A[2][2])%MOD;
    p22=(A[2][1]*A[1][2]+A[2][2]*A[2][2])%MOD;
    A[1][1]=p11;
    A[1][2]=A[2][1]=p12;
    A[2][2]=p22;
}
void prod1()
{
    p11=(Sol[1][1]*A[1][1]+Sol[1][2]*A[2][1])%MOD;
    p12=(Sol[1][1]*A[1][2]+Sol[1][2]*A[2][2])%MOD;
    p22=(Sol[2][1]*A[1][2]+Sol[2][2]*A[2][2])%MOD;
    Sol[1][1]=p11;
    Sol[1][2]=Sol[2][1]=p12;
    Sol[2][2]=p22;
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    A[1][1]=0;A[1][2]=1;
    A[2][2]=1;A[2][1]=1;
    Sol[1][1]=1;
    Sol[2][2]=1;
    scanf("%lld",&k);
    for(;k;k>>=1)
    {
        if(k&1)prod1();
        prod2();
    }
    printf("%lld",Sol[2][1]);
    return 0;
}