#include <fstream>
using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
long long p[3][3],a[3][3],c[3][3];
int n;
short int i,j,k;
void prod (long long a[3][3],long long b[3][3])
{
    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]+=a[i][k]*b[k][j];
                c[i][j]%=666013;
            }
        }
    }
    for (i=1; i<=2; i++)
    {
        for (j=1; j<=2; j++)
            a[i][j]=c[i][j];
    }
}
int main ()
{
    fin>>n;
    if (n<=2)
    {
        fout<<1;
        return 0;
    }
    n-=2;
    a[1][1]=1;
    a[1][2]=1;
    a[2][1]=1;
    a[2][2]=0;
    p[1][1]=1;
    p[1][2]=0;
    p[2][1]=0;
    p[2][2]=1;
    while (n!=0)
    {
        if (n%2==1)
            prod (p,a);
        prod (a,a);
        n=n/2;
    }
    fout<<(p[1][1]+p[1][2])%666013;
    return 0;
}