#include <iostream>
#include <fstream>
#include <assert.h>
#include <string.h>

using namespace std;

#define mod 666013

ifstream fi("kfib.in");
ofstream fo("kfib.out");

int sol[3][3];
int n;

void mult(int a[3][3],int b[3][3],int c[3][3])
{
    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]+1LL*a[i][k]*b[k][j])%mod;
}

void lg(int p)
{
    int aux[3][3];
    int c[3][3];

    c[0][0]=0;
    c[1][1]=c[0][1]=c[1][0]=1;

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

    while(p)
    {
        if(p%2)
        {
            memset(aux,0,sizeof(aux));
            mult(sol,c,aux);
            memcpy(sol,aux,sizeof(aux));
        }

        memset(aux,0,sizeof(aux));
        mult(c,c,aux);
        memcpy(c,aux,sizeof(aux));
        p/=2;
    }

    cout<<sol[1][1];

}

int main()
{
    fi>>n;

    lg(n-1);

    return 0;
}