#include <bits/stdc++.h>
using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

const long long MOD = 666013;

long long ma1[3][3],ma2[3][3];
long long n;

void ridicare(long long mat1[][3],long long mat2[][3])
{
    long long sol[3][3];
    for(long long i=1;i<=2;++i)
        for(long long j=1;j<=2;++j)
    {
        long long val=0;
        for(long long k=1;k<=2;++k)
            val+=(1LL*mat1[i][k]*mat2[k][j]);
        sol[i][j]=val%MOD;
    }

    for(long long i=1;i<=2;++i)
        for(long long j=1;j<=2;++j)
            mat1[i][j]=sol[i][j];

}

int main()
{
    f>>n;
    long long f[3];
    f[0]=0;
    f[1]=1;
    f[2]=1;
    ma2[1][1]=ma2[2][2]=1;
    ma1[1][2]=ma1[2][2]=ma1[2][1]=1;
    if(n==1 || n==0 || n==2)
    {
        g<<f[n];
        return 0;
    }
    n--;
    while(n)
    {
        if(n%2)
        {
            n--;
            ridicare(ma2,ma1);
        }
        n/=2;
        ridicare(ma1,ma1);
    }

    g<<ma2[2][2];

}