#include <bits/stdc++.h>
#define ll long long
#define MOD 666013
using namespace std;
map <ll ,ll> M;
ll N;
ll Kfib(ll n)
{
    if(M[n]) return M[n]%MOD;
    return M[n] =(Kfib((n+1)/2) * Kfib(n/2) + Kfib((n-1)/2)*Kfib((n-2)/2))%MOD;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    M[0] = M[1] = 1;
    cin >> N;
    cout << Kfib(N-1)%MOD;
    return 0;
}