#include <iostream>
#include <fstream>
using namespace std;
const int M = 666013;
long long m1[3][3],m2[3][3];

void produs(long long  a[3][3], long long b[3][3], int n)
{
    long long aux[3][3];

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            aux[i][j]=0;
            for(int k=1;k<=n;k++)
            {
                aux[i][j]+=a[i][k]*b[k][j];
            }
        }
  }

  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        a[i][j]=aux[i][j] % M;
}


int main()
{
    long long k;
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&k);
    m1[1][2]=m1[2][1]=m1[2][2]=1;
    m2[1][1]=m2[2][2]=1;
    k--;
    while(k>0){

      if(k%2!=0) {
        produs(m2,m1,2);
      }
      k/=2;
      produs(m1,m1,2);
    }
    printf("%lld",m2[2][2]);
    return 0;
}