#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define MOD 666013
using namespace std;
using ll = long long;
template<typename T, size_t M, size_t N>
using matrix = array<array<T,M>,N>;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
matrix<ll,2,2> rec = {1,1,1,0};
void multiplyMatrix (matrix<ll,2,2>& c, const matrix<ll,2,2> a, const matrix<ll,2,2> b) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = 0;
for (int k = 0; k < 2; k++) {
c[i][j] += (1ll * a[i][k] * b[k][j]) % MOD;
}
}
}
}
void lgPut (matrix<ll,2,2>& c, int pw) {
while (pw) {
if (pw&1) {
multiplyMatrix(c,rec,c);
}
multiplyMatrix(rec,rec,rec);
pw >>= 1;
}
}
int main() {
int n;
fin >> n;
if (n == 0) {
fout << 0;
return 0;
} else if (n == 1) {
fout << 1;
return 0;
}
matrix<ll,2,2> ans = {1,1,0,0};
lgPut(ans,n-1);
fout << ans[0][0];
return 0;
}