#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 a, matrice b)
{
    matrice v;
    v.a=(a.a*b.a+a.b*b.c)%mod;
    v.b=(a.a*b.b+a.b*b.d)%mod;
    v.c=(a.c*b.a+a.d*b.c)%mod;
    v.d=(a.c*b.b+a.d*b.d)%mod;
    return v;
}
matrice z={0,1,1,1};
matrice ridicare(matrice z,long long i)
{
    if(i==0)
    return z;
    if(i%2==0)
        return ridicare(inmultre(z,z),i/2);
    else
        return inmultre(z,ridicare(inmultre(z,z),i/2));

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