#include <fstream>
#define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
struct matrice{
    long long a,b,c,d;
};
matrice inmultre(matrice X, matrice Y)
{
    matrice V;
    V.a=(X.a*Y.a + X.b*Y.c)%mod;
    V.b=(X.a*Y.b + X.b*Y.d)%mod;
    V.c=(X.c*Y.a + X.d*Y.c)%mod;
    V.d=(X.c*Y.b + X.d*Y.d)%mod;
    return V;
}
matrice z={0,1,1,1};
matrice logridicare(matrice z,long long i)
{
    if(i==0)
    return {1,0,0,1};
    if(i%2==0)
        return logridicare(inmultre(z,z),i/2);
    else
        return inmultre(z,logridicare(inmultre(z,z),i/2));

}
int main(void)
{
    long long k;
    f>>k;
    if(k==0)
        g<<0;
    else
        {
            matrice rez=logridicare(z,k-1);
            g<<rez.d;
        }
    f.close();
    g.close();
    return 0;
}