#include <fstream>
#include <cmath>
#define XYZ 666013
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
int k,a[1400001],n;

void Fibo()
{
    int i;
    a[0]=0; a[1]=a[2]=1;
    i=2;
    while(!(a[i]==1 && a[i-1]==0))
    {
       i++;
       a[i]=(a[i-1]+a[i-2])%XYZ;
    }
    n=i-1;
}

int main()
{
    cin>>k;
    Fibo();
    cout<<a[k%n]<<"\n";
    cin.close();
    cout.close();
    return 0;
}