#include <bits/stdc++.h>
#define pb push_back
#define mod 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
vector<vector<int>> inmultire(vector<vector<int>> &mat1, vector<vector<int>> &mat2)
{
vector<vector<int>> res;
int m1 = mat1[0].size(), n1 = mat1.size();
int m2 = mat2[0].size(), n2 = mat2.size();
for(int i=0; i<n1; i++)
{
vector<int> aux;
for(int j=0; j<m2; j++)
{
int r = 0;
for(int k=0; k<m1; k++)
r=(r+((long long)mat1[i][k]*mat2[k][j]%mod))%mod;
aux.pb(r);
}
res.pb(aux);
}
return res;
}
vector<vector<int>> ridicare(vector<vector<int>> &mat, int p)
{
vector<vector<int>> res = mat;
for(int i=0; i<res.size(); i++)
for(int j=0; j<res.size(); j++)
res[i][j] = (i==j) ? 1 : 0;
while(p!=0)
{
if(p%2!=0)
{
res = inmultire(mat, res);
}
mat = inmultire(mat, mat);
p/=2;
}
return res;
}
int main()
{
int n;
fin>>n;
vector<vector<int>> z; vector<int> aux;
aux.pb(0); aux.pb(1); z.pb(aux);
aux[0]=1; z.pb(aux);
vector<vector<int>> sol;
sol = ridicare(z, n-1);
fout<<sol[1][1];
}