# include <fstream>
# include <algorithm>
# define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int i,j,k;
int a[2][2], b[2][2], mat[2][2];
void multiplica (int a[][2], int b[][2])
{
    int c[2][2];
    c[0][0]= (1LL*a[0][0] * b[0][0] + 1LL*a[0][1] * b[1][0])%mod;
    c[0][1]= (1LL*a[0][0] * b[0][1] + 1LL*a[0][1] * b[1][1])%mod;
    c[1][0]= (1LL*a[1][0] * b[0][0] + 1LL*a[1][1] * b[1][0])%mod;
    c[1][1]= (1LL*a[1][0] * b[0][1] + 1LL*a[1][1] * b[1][1])%mod;

    a[0][0]=c[0][0];
    a[0][1]=c[0][1];
    a[1][0]=c[1][0];
    a[1][1]=c[1][1];
}
int main ()
{
    b[0][0]=0; b[0][1]=1;
    b[1][0]=1; b[1][1]=1;

    mat[0][0]=mat[1][1]=1;

    f>>k; --k;
    while (k)
    {
        if (k%2==0)
        {
            multiplica (b, b);
            k=k/2;
        }
        else {
                 multiplica (mat, b);
                 --k;
             }
    }

    g<<mat[1][1]<<"\n";

    return 0;
}