#include <cstdio>
#include <cstring>

using namespace std;

const int MOD = 666013;

int n;
int mat[3][3][3] , res[3][3] , crt[3][3] , aux[3][3];

void inmMat(int A[3][3] , int B[3][3] , int C[3][3] , int lim1 , int lim2)
{
    A[1][1] = A[1][2] = A[2][1] = A[2][2] = 0;
    for (int i = 1; i <= lim1; ++i)
        for (int j = 1; j <= lim2; ++j)
            for (int k = 1; k <= 2; ++k)
                A[i][j] = (1LL * A[i][j] + 1LL * B[i][k] * C[k][j]) % MOD;
}

void lgPut(int P)
{
    memcpy(crt , mat[2] , sizeof(mat[2]));

    for (int i = 0; (1 << i) <= P; ++i)
    {
        if (((P & (1 << i)) >> i) == 1)
        {
            inmMat(aux , res , crt , 2 , 2);
            memcpy(res , aux , sizeof(aux));
        }

        inmMat(aux , crt , crt , 2 , 2);
        memcpy(crt , aux , sizeof(aux));
    }

    memcpy(mat[2] , res , sizeof(res));
}

void init()
{
    mat[1][1][1] = 1; mat[1][1][2] = 1;

    mat[2][1][1] = 0; mat[2][1][2] = 1;
    mat[2][2][1] = 1; mat[2][2][2] = 1;

    res[1][1] = 1; res[1][2] = 0;
    res[2][1] = 0; res[2][2] = 1;
}


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

    scanf("%d", &n);
    if (n == 1)
    {
        printf("1\n");
        return 0;
    }

    init(); lgPut(n-1);

    inmMat(res , mat[1] , mat[2] , 1 , 2);
    printf("%d\n", res[1][1]);

    return 0;
}