//#include <iostream>
#include<stdio.h>
using namespace std;
int a[3][3],b[3][3],i,j,n;
void patrat()
{
    int x[3][3],i,j;
    x[1][1]=a[1][1]*a[1][1]+a[2][1]*a[1][2];
    x[1][2]=a[1][2]*(a[1][1]+a[2][2]);
    x[2][1]=a[2][1]*(a[1][1]+a[2][2]);
    x[2][2]=a[1][2]*a[2][1]+a[2][2]*a[2][2];
    for(i=1;i<=2;i++)
    for(j=1;j<=2;j++)
    a[i][j]=x[i][j]%666013;
}
void produs()
{
 int x[3][3],i,j;

    x[1][1]=a[1][1]*b[1][1]+b[2][1]*a[1][2];
    x[1][2]=a[1][1]*b[1][2]+a[1][2]*b[2][2];
    x[2][1]=a[2][1]*b[1][1]+a[2][2]*b[2][1];
    x[2][2]=a[1][2]*a[2][1]+a[2][2]*b[2][2];
    for(i=1;i<=2;i++)
    for(j=1;j<=2;j++)
    a[i][j]=x[i][j];
}
void fib(int x)
{

    if(x%2==0)
     patrat();
    else
    {
        patrat();
        produs();
    }




}
int main()
{
  freopen("kfib.in","r",stdin);
  freopen("kfib.out","w",stdout);
  scanf("%d",&n);
  a[2][1]=1;a[1][2]=1;
  a[2][2]=1;
  b[2][1]=1;
  b[1][2]=1;
  b[2][2]=1;
  fib(n);
 /*  for(i=1;i<=2;i++)
    for(j=1;j<=2;j++)
    printf("%d",a[i][j]);
*/
printf("%d",a[2][2]);
    return 0;
}