#include <cstdio>
#include <iostream>

using namespace std;
FILE *fin, *fout;

const int NMAX = 5;
const int MOD = 666013;

int C[NMAX][NMAX];

void copy_matrix(int dest[NMAX][NMAX], int src[NMAX][NMAX], int length)
{
    for(int i = 1; i <= length; i++)
        for(int j = 1; j <= length; j++)
            dest[i][j] = src[i][j];
}

void matrix_product(int A[NMAX][NMAX], int B[NMAX][NMAX], int C[NMAX][NMAX], int n)
{
    int i, j, k, AUX[NMAX][NMAX] = {0};

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

    copy_matrix(C, AUX, n);
}

void matrix_lgput(int A[NMAX][NMAX], int B[NMAX][NMAX], int n, int exp)
{
    int AUX[NMAX][NMAX];

    copy_matrix(AUX, A, n);

    if(exp == 1 or exp == 0)
    {
        copy_matrix(B, A, n);
        return;
    }

    if(exp % 2 == 1)
    {
        matrix_lgput(A, AUX, n, (exp - 1));

        matrix_product(A, AUX, B, n);
    }
    else
    {
        matrix_lgput(A, AUX, n, exp / 2);

        matrix_product(AUX, AUX, B, n);
    }
}

void print_matrix(int n, int C[NMAX][NMAX])
{
    int i, j;

    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= n; j++)
            fprintf(fout, "%d ", C[i][j]);

        fprintf(fout, "\n");
    }
}

int main()
{
    fin = fopen("kfib.in", "r");
    fout = fopen("kfib.out", "w");

    int FIBO[NMAX][NMAX];

    FIBO[1][1] = 0;
    FIBO[1][2] = 1;
    FIBO[2][1] = 1;
    FIBO[2][2] = 1;

    int n;
    fscanf(fin, "%d", &n);

    if(n == 0)
    {
        fprintf(fout, "0");
        return 0;
    }

    matrix_lgput(FIBO, C, 2, n - 1);

    //print_matrix(2, C);

    fprintf(fout, "%d", C[2][2]);

   /* int M[5][5];

    for(int i = 1; i <= 3; i++)
        for(int j = 1; j <= 3; j++)
        M[i][j] = max(i , j);

    matrix_lgput(M , C , 3 , 6);

    print_matrix(3 , C);
*/
    fclose(fin);
    fclose(fout);
    return 0;
}