#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
int N;
void multiplica(int T[2][2], int M[2][2]){
     long long a = T[0][0]*M[0][0] + T[0][1]*M[1][0];    
     long long b = T[0][0]*M[0][1] + T[0][1]*M[1][1];
     long long c = T[1][0]*M[0][0] + T[1][1]*M[1][0];
     long long d = T[1][0]*M[0][1] + T[1][1]*M[1][1];
     T[0][0] = a%MOD;
     T[0][1] = b%MOD;
     T[1][0] = c%MOD;
     T[1][1] = d%MOD;
}
void power(int T[2][2], int N){
     int 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){
    int 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;
}