#include <cstdio>
using namespace std;
int k;
long long a[3][3], rez[3][3], cop[3][3];
const int MOD=666013;
void inmultire(long long a1[3][3], long long b[3][3], long long c[3][3])
{
c[1][1]=0;
c[1][2]=0;
c[2][1]=0;
c[2][2]=0;
for(int i=1; i<=2; i++)
{
for(int j=1; j<=2; j++)
{
int s=0;
for(int k=1; k<=2; k++)
c[i][j]=(c[i][j]+((1LL*a1[i][k]*b[k][j])%MOD))%MOD;
}
}
}
int inloc(long long a1[3][3], long long b[3][3])
{
a1[1][1]=b[1][1];
a1[1][2]=b[1][2];
a1[2][1]=b[2][1];
a1[2][2]=b[2][2];
for(int i=1;i<=2; i++)
for(int j=1;j<=2;j++)
{
b[i][j]=0;
}
}
int putere(int p)
{
rez[1][1]=1;
rez[1][2]=0;
rez[2][1]=0;
rez[2][2]=1;
while(p)
{
if(p%2==1)
{
p--;
inmultire(rez,a,cop);
inloc(rez,cop);
continue;
}
p/=2;
inmultire(a, a, cop);
inloc(a, cop);
}
long long s=(1LL*rez[1][1]+rez[2][1])%MOD;
return s;
}
int main()
{
freopen("kfib.in", "r", stdin);
freopen("kfib.out", "w", stdout);
a[1][1]=1;
a[1][2]=1;
a[2][1]=1;
a[2][2]=0;
int k;
scanf("%d", &k);
printf("%d", putere(k-2));
return 0;
}