//#include <iostream>
#include<stdio.h>
using namespace std;
long a[3][3],b[3][3],i,j,n;
long p(long x,long y)
{
    long m=(x*y/100%666013)*100+x*y%100;
        return m%666013;
}
void patrat()
{
    long x[3][3],i,j;
    x[1][1]=p(a[1][1],a[1][1])+p(a[2][1],a[1][2]);
    x[1][2]=p(a[1][2],(a[1][1]+a[2][2])%666013);
    x[2][1]=p(a[2][1],(a[1][1]+a[2][2])%666013);
    x[2][2]=p(a[1][2],a[2][1])+p(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 echilibrare()
{

    if(a[1][2]<0&&a[2][1]>0)
        a[1][2]=a[2][1];
    if(a[2][1]<0&&a[1][2]>0)
    a[2][1]==a[1][2];
    if(a[1][1]<0&&a[1][2]>0&&a[2][2]>0)
    a[1][1]=a[2][2]-a[1][2];
    if(a[2][2]<0&&a[1][1]>0&&a[1][2]>0)
    a[2][2]=a[1][1]+a[1][2];
}
void produs()
{
 long 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]=b[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]%666013;
}
void fib(int x)
{

    if(x!=1)
    {


    fib(x/2);
    if(x%2==0)



         patrat();



    else
    {
        patrat();
        produs();
    }

echilibrare();


    }
}
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);

printf("%ld\n",a[1][2]%666013);
    return 0;
}