#include <cstdio>
#define MOD 666013
using namespace std;
int A[3][3], M[3][3];
void sum (int p)
{
    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])%MOD;
        y=(A[1][1]*A[1][2]+A[1][2]*A[2][2])%MOD;
        z=(A[2][1]*A[1][1]+A[2][2]*A[2][1])%MOD;
        t=(A[2][1]*A[1][2]+A[2][2]*A[2][2])%MOD;
        A[1][1]=x; A[1][2]=y; A[2][1]=z; A[2][2]=t;
    }
    x=(M[1][1]*A[1][1]+M[1][2]*A[2][1])%MOD;
    y=(M[1][1]*A[1][2]+M[1][2]*A[2][2])%MOD;
    z=(M[2][1]*A[1][1]+M[2][2]*A[2][1])%MOD;
    t=(M[2][1]*A[1][2]+M[2][2]*A[2][2])%MOD;
    M[1][1]=x; M[1][2]=y; M[2][1]=z; M[2][2]=t;
}
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;
}