#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
const int mod = 666013;
int a[3][3],F[3],rez[3];
void inmultire_matrice()
{

    //v=new int[3];
    int p,q;
    if(F[0]<mod && F[1]<mod)
    {
    p=(F[0]*a[0][0]+F[1]*a[1][0]);///%mod;
    q=(F[0]*a[0][1]+F[1]*a[1][1]);///%mod;
    }
    else
    {
    p=((F[0]%mod)*a[0][0]+(F[1]%mod)*a[1][0])%mod;
    q=((F[0]%mod)*a[0][1]+(F[1]%mod)*a[1][1])%mod;
    }
    F[0]=p;
    F[1]=q;
    cout<<'\n';
    //return v;
}
int main()
{
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    int k,i,j;
    fin>>k;
    for(i=0;i<=1;i++)
    {for(j=0;j<=1;j++)
        if(i+j==0)
        {
            a[i][j]=0;
        }
        else
        {
            a[i][j]=1;
        }
    }
 //   cout<<a[0][0]<<' '<<a[0][1]<<' '<<a[1][0]<<' '<<a[1][1]<<' ';
    F[0]=1;
    F[1]=1;
    for(i=1;i<=k-2;i++)
    {
        inmultire_matrice();
      /*  for(j=0;j<=1;j++)
        {
            cout<<F[j]<<' ';
        }*/
    }
    fout<<F[1];
    fin.close();
    fout.close();
    return 0;
}