#include <bits/stdc++.h>
#define MOD 666013
typedef long long ll;
struct mat{
    ll a, b, c, d;
};
ll k, a, b;
mat sol[35];
mat multiply(mat m1, mat m2);
int main()
{
    std::cin>>k;
    sol[0]={1LL, 0LL, 0LL, 1LL};
    sol[1]={0LL, 1LL, 1LL, 1LL};
    for(int i=2; i<=33; ++i) sol[i]=multiply(sol[i-1], sol[i-1]);
    --k;
    a=0LL, b=1LL;
    while(k){
        ll nr=int(log2(k));
        k=k-(1LL<<nr);
        ll xa, xb;
        xa=((a*sol[nr+1].a)%MOD+(b*sol[nr+1].c)%MOD)%MOD;
        xb=((a*sol[nr+1].b)%MOD+(b*sol[nr+1].d)%MOD)%MOD;
        a=xa; b=xb;
    }
    std::cout<<b;
    return 0;
}
mat multiply(mat m1, mat m2){
    mat m;
    m.a=((m1.a*m2.a)%MOD+(m1.b*m2.c)%MOD)%MOD;
    m.b=((m1.a*m2.b)%MOD+(m1.b*m2.d)%MOD)%MOD;
    m.c=((m1.c*m2.a)%MOD+(m1.d*m2.c)%MOD)%MOD;
    m.d=((m1.c*m2.b)%MOD+(m1.d*m2.d)%MOD)%MOD;
    return m;
}