#include <bits/stdc++.h>
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

const int MOD=666013;

long long k;
long long a[15][15],b[15][15],c[15][15];

void inmultire(long long a[15][15],long long b[15][15],long long c[15][15])
{
    int i,j,k;

    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
        {
            c[i][j]=0;
            for(k=1;k<=2;k++)
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;
        }
}

void putere(long long a[15][15],long long n)
{
    long long i,j;

    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
            b[i][j]=(i==j);

    while(n)
    {
        if(n%2)
        {
            inmultire(b,a,c);
            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)
                    b[i][j]=c[i][j];
        }

        inmultire(a,a,c);
        for(i=1;i<=2;i++)
            for(j=1;j<=2;j++)
                a[i][j]=c[i][j];

        n/=2;
    }
}

int main()
{
    fin>>k;

    if(k==0)
    {
        fout<<0;
        return 0;
    }

    a[1][1]=0;
    a[1][2]=1;
    a[2][1]=1;
    a[2][2]=1;

    putere(a,k-1);

    fout<<b[2][2];

    return 0;
}