#include <iostream>
#include <fstream>
using namespace std;
#define M 666013
ifstream f("kfib.in");
ofstream g("kfib.out");
long long a[2][2]={{0,1},{0,0}};
long long c[2][2]={{0,1},{1,1}};
long long sol[2][2]={{1,0},{0,1}};
int n;
void inmultire(long long a[2][2], long long b[2][2])
{long long c[2][2],i,j,k;
for(i=0;i<2;i++)
for(j=0;j<2;j++)
{c[i][j]=0;
for(k=0;k<2;k++) c[i][j]+=a[i][k]*b[k][j];
c[i][j]=c[i][j]%M;
}
for(i=0;i<2;i++)
for(j=0;j<2;j++) a[i][j]=c[i][j];
}
void putere(long long sol[2][2], int n)
{while(n)
{if(n%2==1) {inmultire (sol,c); n--; }
else { inmultire(c,c); n/=2; }
}
}
int main()
{f>>n;
putere(sol,n);
inmultire(a,sol);
g<<a[0][0];
return 0;
}