#include <bits/stdc++.h>
#define MAX 3
#define FILES freopen("kfib.in","r",stdin);\
freopen("kfib.out","w",stdout);
#define mod 666013
#define int long long
using namespace std;
int fibo[MAX][MAX], dp[MAX][MAX], n;
void inm(int A[MAX][MAX], int B[MAX][MAX])
{
int rez[MAX][MAX] = {0};
for(int i = 1;i <= 2; ++i)
{
for(int j = 1;j <= 2; ++j)
{
for(int k = 1;k <= 2; ++k)
rez[i][j] = (rez[i][j] + A[i][k] * B[k][j]) % mod;
}
}
for(int i = 1;i <= 2; ++i)
for(int j = 1;j <= 2; ++j)
A[i][j] = rez[i][j];
}
void exp_rapid(int e)
{
while(e)
{
if(e & 1)
inm(fibo, dp);
inm(dp, dp);
e >>= 1;
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
FILES
std::cin >> n;
fibo[1][1] = fibo[1][2] = 1;
dp[1][1] = dp[1][2] = dp[2][1] = 1;
if(n == 1 || n == 2)
std::cout << 1;
else{
exp_rapid(n - 2);
std::cout << fibo[1][1];
}
}