#include <iostream>
#include <fstream>
#define mn 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
unsigned long long k;
struct M2{int a[2][2];}O2,F;
M2 MI(M2 A,M2 B)
{
    M2 C=O2;
    for(int i=0;i<=1;++i)
    {
        for(int j=0;j<=1;++j)
        {
            unsigned long long t=0;
            for(int q=0;q<=1;++q)t=t+A.a[i][q]*B.a[q][j];
            t=t%mn;
            C.a[i][j]=t;
        }
    }
    return C;
}
M2 riptl(M2 M,unsigned long long k)
{
    if(k==1)return M;
    if(k%2==0)return riptl(MI(M,M),k/2);
    return MI(M,riptl(MI(M,M),k/2));
}
int main()
{
    f>>k;
    if(k==0){g<<0;return 0;}
    if(k<=2){g<<1;return 0;}
    F.a[1][0]=1;F.a[0][1]=1;F.a[1][1]=1;
    M2 K=riptl(F,k-1);
    g<<K.a[1][1];
}