#include <stdio.h>
#include <stdlib.h>

#define MOD 666013

long long A[2][2],P[2][2],X[2][2];

void inmultire(long long a[2][2],long long b[2][2],long long c[2][2])
{
    int i,j,k;
    long long s;
    for(i=0;i<2;i++)
    {
        for(j=0;j<2;j++)
        {
            s=0;
            for(k=0;k<2;k++)
                s=(s+a[i][k]*b[k][j])%MOD;
            c[i][j]=s;
        }
    }
}

int main()
{
    FILE *f,*out;
    long long n;
    if((f=fopen("kfib.in","r"))==NULL)
    {
        perror("Nu se poate deschide fisierul.");
        exit(-1);
    }
    if((out=fopen("kfib.out","w"))==NULL)
    {
        perror("Nu se poate deschide fisierul.");
        exit(-1);
    }
    fscanf(f, "%lld", &n);
    for(int i=0;i<2;i++)
    {
        P[i][0]=0;
        P[i][1]=0;
        P[i][i]=1;
        for(int j=0;j<2;j++)
            A[i][j]=1;
    }
    A[0][0] = 0;
    while(n!=0)
    {
        if(n%2==1)
        {
            inmultire(P,A,X);
            for(int i=0;i<2;i++)
                for(int j=0;j<2;j++)
                    P[i][j]=X[i][j];
        }
        inmultire(A,A,X);
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                A[i][j]=X[i][j];
        n=n/2;
    }
    fprintf(out,"%lld\n",P[0][1]);
    fclose(f);
    fclose(out);
    return 0;
}