#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>
#include <cstring>
using namespace std;
int mod=666013;
int f(int a[][3],int b[][3],int c[][3])
{
    int i,j,k;
    memset(c,0,9*sizeof(int));
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
        {
            for(k=1;k<=2;k++)
                c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j]%mod)%mod;
        }
}


int main()
{
    freopen ("kfib.in","r",stdin);
    freopen ("kfib.out","w",stdout);
    int n,aux[3][3],prod[3][3],r[3][3],i,v[33],c=0,j,k;
    scanf("%d",&n);
    if(n==0)
    {printf("0");
    return 0;}
    n--;
    while(n)
    {
        v[c++]=n%2;
        n/=2;
    }
    prod[1][1]=1;
    prod[1][2]=0;
    prod[2][1]=0;
    prod[2][2]=1;
    r[1][1]=0;
    r[1][2]=r[2][1]=r[2][2]=1;
    for(i=0;i<c;i++)
    {
        if(v[i])
            f(prod,r,aux);
        if(v[i])
        {
            for(j=1;j<=2;j++)
                for(k=1;k<=2;k++)
                prod[j][k]=aux[j][k];
        }
        f(r,r,aux);
         for(j=1;j<=2;j++)
                for(k=1;k<=2;k++)
                r[j][k]=aux[j][k];
    }
    printf("%d",prod[2][2]);












    return 0;
}