#include <bits/stdc++.h>
#define MOD 666013
#define ll long long
using namespace std;
int N;
void multiplica(ll T[2][2], ll M[2][2]){
     ll a = (T[0][0]*M[0][0] + T[0][1]*M[1][0])%MOD;    
     ll b = (T[0][0]*M[0][1] + T[0][1]*M[1][1])%MOD;
     ll c = (T[1][0]*M[0][0] + T[1][1]*M[1][0])%MOD;
     ll d = (T[1][0]*M[0][1] + T[1][1]*M[1][1])%MOD;
     T[0][0] = a%MOD;
     T[0][1] = b%MOD;
     T[1][0] = c%MOD;
     T[1][1] = d%MOD;
}
void power(ll T[2][2], int N){
    ll M[2][2] = {{1,1},{1,0}};
     if(N == 0 || N == 1) return;
     power(T, N/2);
     multiplica(T,T);
     if(N%2!=0) multiplica(T, M);
}
int kfib(int N){
    ll T[2][2] = {{1,1},{1,0}}; 
    power(T, N-1);
    return T[0][0]%MOD;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);    
    assert(freopen("kfib.in","r", stdin));
    assert(freopen("kfib.out","w", stdout));
    cin >> N;
    cout << kfib(N);
    return 0;
}