#include <bits/stdc++.h>
#define modulo  666013
#define nmax 1400000
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int a[nmax+5],n;
int main()
{
    int k;
    bool gata;
    gata=false;
    fin>>n;
    a[0]=0;
    a[1]=a[2]=1;
    k=2;
    while(!gata)
    {
        k++;
        a[k]=a[k-1]+a[k-2];
        if(a[k]>=modulo)
            a[k]-=modulo;
        if(a[k]==1 && a[k-1]==0)
            gata=true;
    }
    k--;
    fout<<a[n%k]<<"\n";
    fin.close();
    fout.close();
    return 0;
}