#include <cstdio>
#include <cstring>
#define mod 666013
#define ll long long
using namespace std;
FILE*f=fopen("kfib.in","r");
FILE*g=fopen("kfib.out","w");
ll A[3][3],P[3][3],n,AUX[3][3];
void multi(ll a[3][3],ll b[3][3],ll c[3][3])
{
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;
}
void lqpowa(int n,ll m[3][3])
{
    m[0][0]=m[1][1]=1;
    for(int i=0; (1 << i) <= n;i++)
    {
        if((1 << i) & n)
        {
            memset(AUX,0,sizeof(AUX));
            multi(m,P,AUX);
            memcpy(m,AUX,sizeof(AUX));
        }
        memset(AUX,0,sizeof(AUX));
        multi(P,P,AUX);
        memcpy(P,AUX,sizeof(AUX));
    }
}
int main()
{
    fscanf(f,"%d",&n);
    P[0][0]=0; P[0][1]=1; P[1][0]=1; P[1][1]=1;
    lqpowa(n-1,A);
    fprintf(g,"%d\n",A[1][1]);
    return 0;
}