#include <stdio.h>
#include <string.h>
using namespace std;
#define mod 666013

void multiply(int a[][3], int b[][3], int c[][3]);
void lgPower(int power, int m[][3]);

FILE *in,*out;

int n;
int matrix[3][3], solution[3][3];

int main()
{
    in=fopen("kfib.in","rt");
    out=fopen("kfib.out","wt");

    fscanf(in,"%d",&n);

    matrix[0][0] = 0;
    matrix[0][1] = matrix[1][0] = matrix[1][1] = 1;

    lgPower(n-1, solution);

    fprintf(out,"%d",solution[1][1]);

    fclose(in);
    fclose(out);
    return 0;
}

void multiply(int a[][3], int b[][3], int c[][3])
{
    for(int i=0; i<2; ++i)
        for(int j=0; j<2; ++j)
            for(int k=0; k<2; ++k)
                c[i][j] = (c[i][j] + 1LL*a[i][k]*b[k][j]) % mod;
}

void lgPower(int power, int m[][3])
{
    int aux[3][3], contor[3][3];
    memcpy(contor, matrix, sizeof(matrix));
    m[0][0] = m[1][1] = 1;

    for(int i=0 ; (1<<i)<=power; ++i)
    {
        if((1<<i)&power)
        {
            memset(aux, 0, sizeof(aux));
            multiply(m, contor, aux);
            memcpy(m, aux, sizeof(aux));
        }
        memset(aux, 0, sizeof(aux));
        multiply(contor, contor, aux);
        memcpy(contor, aux, sizeof(contor));
    }
}