#include <bits/stdc++.h>
#define L long long
#define NM 1000000
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
unsigned L n;
struct m2
{
    L a,b,c,d;
};
struct m1
{
    L a,b;
};
m2 inm(m2 a,m2 b)
{
    m2 c;
    c.a=(a.a*b.a+a.b*b.c)%666013;
    c.b=(a.a*b.b+a.b*b.d)%666013;
    c.c=(a.c*b.a+a.d*b.c)%666013;
    c.d=(a.c*b.b+a.d*b.d)%666013;
    return c;
}
m1 inm1(m2 a, m1 b)
{
    m1 c;
    c.a=(a.a*b.a+a.b*b.b)%666013;
    c.b=(a.c*b.a+a.d*b.b)%666013;
    return c;
}
m2 exp(m2 a,L x)
{
    m2 s=a;
    --x;
    while(x)
    {
        if(x%2)
            s=inm(s,a),--x;
        else
            a=inm(a,a),x>>=1;
    }
    return s;
}
int main()
{
    in>>n;
    if (n<=2)
    {
        out<<1;
        return 0;
    }
    m2 d= {1,1,1,0};
    m1 d1= {1,1};
    m1 c=inm1(exp(d,n-2),d1);
    out<<c.a;
}