#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=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            for(int k=1;k<=3;k++)
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;
}
int main()
{
    fscanf(f,"%d",&n);
    n-=2;
    A[1][1]=0;
    A[1][2]=A[2][1]=A[2][2]=1;
    memcpy(P,A,sizeof(A));
    while(n)
    {
        if(n%2==0)
        {
            memset(AUX,0,sizeof(AUX));
            multi(A,A,AUX);
            memcpy(A,AUX,sizeof(AUX));
            n/=2;
        }
        else
        {
            memset(AUX,0,sizeof(AUX));
            multi(P,A,AUX);
            memcpy(P,AUX,sizeof(AUX));
            n--;
        }
    }
    fprintf(g,"%d",P[2][2]);
    return 0;
}