#include <fstream>
#define MOD 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long p[3][3],a[3][3];
int k;
void produs(long long c[3][3], long long d[3][3])
{
    long long x[3][3],s;
    int i,j,l;
    for(i=1;i<=2;i++)
    {
        for(j=1;j<=2;j++)
        {
            s=0;
            for(l=1;l<=2;l++)
            {
                s=(s+c[i][l]*d[l][j])%MOD;
            }
            x[i][j]=s;
        }
    }
    for(i=1;i<=2;i++)
    {
        for(j=1;j<=2;j++)
        {
            c[i][j]=x[i][j];
        }
    }
}
void inmul(long long p[3][3],long long a[3][3], int k)
{
    while (k)
    {
        if(k%2==1)
        {
            produs(p,a);
        }
        produs(a,a);
        k=k/2;
    }
}
int main()
{
    f>>k;
    a[1][1]=0;
    a[1][2]=1;
    a[2][1]=1;
    a[2][2]=1;
    p[1][1]=1;
    p[1][2]=0;
    p[2][1]=0;
    p[2][2]=1;
    inmul(p,a,k);
    g<<p[1][2];
    g.close();
    return 0;
}