#include <cstdio>
#define MOD 666013
using namespace std;
long long int A[3][3], M[3][3];
void sum (int p)
{
    long long int i, x, y, z, t;
    A[1][1]=0; A[1][2]=1; A[2][1]=1; A[2][2]=1;
    for (i=1; i<=p; i++)
    {
        x=A[1][1]*A[1][1]+A[1][2]*A[2][1];
        y=A[1][1]*A[1][2]+A[1][2]*A[2][2];
        z=A[2][1]*A[1][1]+A[2][2]*A[2][1];
        t=A[2][1]*A[1][2]+A[2][2]*A[2][2];
        A[1][1]=x%MOD; A[1][2]=y%MOD; A[2][1]=z%MOD; A[2][2]=t%MOD;
    }
    x=M[1][1]*A[1][1]+M[1][2]*A[2][1];
    y=M[1][1]*A[1][2]+M[1][2]*A[2][2];
    z=M[2][1]*A[1][1]+M[2][2]*A[2][1];
    t=M[2][1]*A[1][2]+M[2][2]*A[2][2];
    M[1][1]=x%MOD; M[1][2]=y%MOD; M[2][1]=z%MOD; M[2][2]=t%MOD;
}
int main()
{
    int k, i=0;
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&k);
    M[1][1]=1; M[1][2]=0; M[2][1]=0; M[2][2]=1;
    if (k==0) {printf("0\n"); return 0;}
    else if (k<3) {printf("1\n"); return 0;}
    else k-=2;
    while (k>0)
    {
        if (k%2==1)
        {
            sum(i);
        }
        k/=2; i++;
    }
    printf("%d\n",(M[1][2]+M[2][2])%MOD);
    return 0;
}