#include<bits/stdc++.h>
#define MOD 666013

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

long long a[3][3],b[3][3],c[3][3],k,sol[3][3];

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

void pow_log(long long n)
{
    while(n>0)
    {
        if(n%2==1)inmultire(sol,b);
        inmultire(b,b);
        n/=2;
    }
}

int main()
{
    f>>k;
    if(k==0)
    {
        g<<0;
        return 0;
    }
    b[1][2]=b[2][1]=b[2][2]=1;
    a[1][2]=1;
    sol[1][1]=sol[2][2]=1;
    pow_log(k-1);
    inmultire(a,sol);
    g<<a[1][2];
}