#include <cstdio>
#define Y 10

const int MOD = 666013;

int ZERO[Y][Y];
int A[Y][Y];
int T[Y][Y];

void Set()
{
    T[0][0] = 1;
    T[0][1] = 2;
    T[1][2] = 1;
    A[0][0] = A[0][1] = 2;
    A[1][2] = A[2][1] = A[2][2] = 1;
}

void Equal(int A[Y][Y], int B[Y][Y])
{
    int i,j;
    for(i = 0; i < Y; ++i)
        for(j = 0; j < Y; ++j)
        A[i][j] = B[i][j];
}

void Mul(int A[Y][Y], int B[Y][Y])
{
    int R[Y][Y];
    int i,j,k;

    Equal(R,ZERO);

    for(i = 1; i <= A[0][0]; ++i)
        for(j = 1; j <= B[0][1]; ++j)
            for(k = 1; k <= A[0][1]; ++k)
            R[i][j] = ( R[i][j] + 1LL * A[i][k] * B[k][j] ) % MOD;

    R[0][0] = A[0][0];
    R[0][1] = B[0][1];
    Equal(A,R);
}

void LgPut(int A[Y][Y], int B)
{
    int X[Y][Y];
    int ok=1;

    while(B>0)
    {
        if(B%2)
            if(ok) Equal(X,A), ok = 0;
            else Mul(X,A);

        Mul(A,A);
        B/=2;
    }
    Equal(A,X);
}

int main(){
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);

    int N;

    scanf("%d",&N);
    Set();
    LgPut(A,N-1);
    Mul(T,A);

    printf("%d\n", T[1][2] );



return 0;
}