#include <iostream>
#define ll long long
#define f first
#define s second
#define M 666013
using namespace std;
pair<pair<ll,ll>, pair<ll,ll>> r={{0,1},{1,1}};
void puterefratee(ll p){
    if(p>1){
        puterefratee(p/2);
        r={{(r.f.f*r.f.f%M+r.s.f*r.f.s%M)%M, (r.s.s*r.f.s%M+r.f.s*r.f.f%M)%M},
           {(r.s.f*r.f.f%M+r.s.s*r.s.f%M)%M, (r.s.s*r.s.s%M+r.s.f*r.f.s%M)%M}};
        if(p&1)
            r={{r.s.f, r.s.s}, {(r.f.f+r.s.f)%M, (r.f.s+r.s.s)%M}};
    }
}
int main(){
    ll n;
    cin>>n;
    puterefratee(n-1);
    cout<<r.s.s;
    return 0;
}