#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

#define modulo 666013

long m[2][2],a[2][2],aux[2][2];
long n;


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

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%i", &n);
    a[0][1]=a[1][0]=a[1][1]=1;
    m[0][1]=m[1][0]=m[1][1]=1;
    n--;
    while(n)
    {
            if(n%2)
            {
                   memset(aux,0,sizeof(aux));
                   inm(m,a,aux);
                   memcpy(m,aux,sizeof(aux));
                   n--;
            }
            memset(aux,0,sizeof(aux));
            inm(a,a,aux);
            memcpy(a,aux,sizeof(aux));
            n=n>>1;
    }
    printf("%ld\n", m[0][1]);
    int i;
    scanf("%i", &i);
    return 0;
}