#include<fstream>
#define M 666013
#include<iostream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long n,k,a[5][5],r[5][5],p;
void ve(long long x[5][5])
{
    long long a=x[1][1];
    long long b=x[1][2];
    long long c=x[2][1];
    long long d=x[2][2];
    x[1][1]=(a*a+b*c)%M;
    x[1][2]=(a*b+b*d)%M;
    x[2][1]=(c*a+d*c)%M;
    x[2][2]=(c*b+d*d)%M;
}
void re(long long x[5][5],long long y[5][5])
{
    long long a=x[1][1];
    long long b=x[1][2];
    long long c=x[2][1];
    long long d=x[2][2];
    long long a1=y[1][1];
    long long b1=y[1][2];
    long long c1=y[2][1];
    long long d1=y[2][2];
    x[1][1]=(a*a1+b*c1)%M;
    x[1][2]=(a*b1+b*d1)%M;
    x[2][1]=(c*a1+d*c1)%M;
    x[2][2]=(c*b1+d*d1)%M;
}
int main()
{
    fin>>k;
    if(k==0)
    {
        fout<<0;
        return 0;
    }
    if(k==1||k==2)
    {
        fout<<1;
        return 0;
    }
    k-=2;
    r[1][1]=r[1][2]=r[2][1]=1;
    r[2][2]=0;
    while(k)
    {
        p=1;
        a[1][1]=a[1][2]=a[2][1]=1;
        a[2][2]=0;
        while(p<=k)
        {
            if(2*p>k)
                break;
            p*=2;
            ve(a);
        }
        k-=p;
        re(r,a);
    }
    fout<<r[1][1];
}