#include <stdio.h>
#define MOD 666013
using namespace std;
int n;
int sol[3][3], A[3][3];

void mul(int a[3][3], int b[3][3])
{
    int aux[4][4];
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++) aux[i][j] = 0;

    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            for(int k=1;k<=2;k++)
            {
                long long t=1LL*a[i][k]*b[k][j];
                aux[i][j]=aux[i][j]+t%MOD;
            }
        }
    }

    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++) a[i][j] = aux[i][j];

}

void power()
{
    int pow = n;

    sol[1][1] = 1;
    sol[1][2] = 0;
    sol[2][1] = 0;
    sol[2][2] = 1;

    while(pow)
    {
        if ( pow % 2 == 1) mul(sol, A);
        mul(A,A);
        pow = pow/2;
    }

}

int main()
{

    FILE*f,*g;
    f=fopen("kfib.in","r");
    g=fopen("kfib.out","w");
    fscanf(f,"%d",&n);

    A[1][1] = 0;
    A[1][2] = 1;
    A[2][1] = 1;
    A[2][2] = 1;

    power();
    int t=sol[2][1]%MOD;
    fprintf(g,"%d\n",t);


}