#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
int sol[2][2]={{0, 1}, {1, 1}};
int m[2][2]={{0, 1}, {1, 1}};
//a b w x a*w+b*y a*x+b*z
//c d y z c*w+d*y c*x+d*z;
const int MOD=666013;
void multiply(int a[2][2], int b[2][2])
{
long long c[2][2];
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]; //% aici e mai costisitor decat adunarea long long
}
c[i][j]%=MOD; //% dureaza > long long
}
}
for (int i=0; i<2; i++) {
for (int j=0; j<2; j++) {
a[i][j]=c[i][j];
}
}
}
int main()
{
int n;
fin>>n;
while (n) {
if (n%2==1) {
multiply(sol, m);
}
multiply(m, m);
n/=2;
}
fout<<sol[0][0];
return 0;
}