#include <fstream>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define cin fin
#define cout fout
const int mod=666013;
int a[2][2]={{1, 1}, {1, 0}};
int I[2][2]={{1, 0}, {0, 1}};
void multmat(int a[][2], int b[][2])
{
    long long c[2][2];
    int i, j, k;
    for (i=0; i<2; i++)
        for (j=0; j<2; j++)
    {
        c[i][j]=0;
        for (k=0; k<2; k++)
            c[i][j]+=1LL*a[i][k]*b[k][j];
    }
    for (i=0; i<2; i++)
        for (j=0; j<2; j++)
        a[i][j]=c[i][j]%mod;9
}

void puteremat(int p)
{
    while (p)
    {
        if (p&1) multmat(I, a);
        multmat(a, a);
        p>>=1;
    }
}
int main()
{
    int k;
    cin>>k;
    if (k<=1) cout<<k;
    else
    {
        puteremat(k-1);
        cout<<I[0][0];
    }
    return 0;
}