# include <iostream>
# include <fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long z[2][2], rez[2][2], a, b, c, d, mod=666013;
void init()
{
    z[0][0]=0;
    z[0][1]=z[1][0]=z[1][1]=1;
    rez[0][0]=rez[1][1]=1;
    rez[0][1]=rez[1][0]=0;
}
void expo(long long exp)
{
    while (exp)
    {

        if (exp & 1)
        {

            a=z[0][0] * rez[0][0] + z[0][1] * rez[1][0];
            b=z[0][0] * rez[0][1] + z[0][1] * rez[1][1];
            c=z[1][0] * rez[0][0] + z[1][1] * rez[1][0];
            d=z[1][0] * rez[0][1] + z[1][1] * rez[1][1];

            rez[0][0]=a%mod;
            rez[0][1]=b%mod;
            rez[1][0]=c%mod;
            rez[1][1]=d%mod;
        }

        a=z[0][0] * z[0][0] + z[0][1] * z[1][0];
        b=z[0][0] * z[0][1] + z[0][1] * z[1][1];
        c=z[1][0] * z[0][0] + z[1][1] * z[1][0];
        d=z[1][0] * z[0][1] + z[1][1] * z[1][1];

        z[0][0]=a%mod;
        z[0][1]=b%mod;
        z[1][0]=c%mod;
        z[1][1]=d%mod;

        exp>>=1;
    }
}

int main()
{
    long long k;
    f>>k;
    k--;
    init();
    expo(k);
    g<<rez[1][1];

    return 0;
}