#include <stdio.h>
#define mod 666013
#define ll long long
void inm(ll a[2][2],ll b[2][2])
{
    ll i,j,k,rez[2][2];
    rez[0][0]=rez[0][1]=rez[1][0]=rez[1][1]=0;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            for(k=0;k<2;k++)
                rez[i][j]=(rez[i][j]+a[i][k]*b[k][j])%mod;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            a[i][j]=rez[i][j];
}
ll p(ll a[2][2],ll n)
{
    ll x[2][2];
    x[0][0]=x[0][1]=x[1][0]=x[1][1]=1;
    while(n!=0)
    {
        if(n%2==1)
            inm(x,a);
        inm(a,a);
        n/=2;
    }
    return x[1][1];
}
ll k,fib[2][2];
int main()
{
    FILE*f1,*f2;
    f1=fopen("kfib.in","r");
    f2=fopen("kfib.out","w");
    fscanf(f1,"%ld",&k);
    fib[0][1]=fib[1][0]=fib[1][1]=1;
    fprintf(f2,"%ld",p(fib,k-2));
    return 0;
}