#include <bits/stdc++.h>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long k,i;
const long long rest=666013;
long long matrix[2][2]={0,1,1,1};
long long ans[2][2]={1,0,0,1};
long long aux[2][2];
int main()
{
    fin>>k;
    if(k==0)
    {
        fout<<0;
        return 0;
    }
    if(k==1)
    {
        fout<<1;
        return 0;
    }
    k--;
    while((1LL<<i)<=k)
    {
        if((1LL<<i)&k)
        {
            k-=(1LL<<i);
            aux[0][0]=(matrix[0][0]*ans[0][0]+matrix[0][1]*ans[1][0])%rest;
            aux[0][1]=(matrix[0][0]*ans[0][1]+matrix[0][1]*ans[1][1])%rest;
            aux[1][0]=(matrix[1][0]*ans[0][0]+matrix[1][1]*ans[1][0])%rest;
            aux[1][1]=(matrix[1][0]*ans[0][1]+matrix[1][1]*ans[1][1])%rest;
            ans[0][0]=aux[0][0];
            ans[0][1]=aux[0][1];
            ans[1][0]=aux[1][0];
            ans[1][1]=aux[1][1];
        }
        aux[0][0]=(matrix[0][0]*matrix[0][0]+matrix[0][1]*matrix[1][0])%rest;
        aux[0][1]=(matrix[0][0]*matrix[0][1]+matrix[0][1]*matrix[1][1])%rest;
        aux[1][0]=(matrix[1][0]*matrix[0][0]+matrix[1][1]*matrix[1][0])%rest;
        aux[1][1]=(matrix[1][0]*matrix[0][1]+matrix[1][1]*matrix[1][1])%rest;
        matrix[0][0]=aux[0][0];
        matrix[0][1]=aux[0][1];
        matrix[1][0]=aux[1][0];
        matrix[1][1]=aux[1][1];
        i++;
    }
    fout<<ans[1][1];
    return 0;
}