#include <bits/stdc++.h>
#define p 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long k;
long long a[4][4],b[4][4],aux[4][4],f[4][4];



int main()
{  fin>>k;
    int i;
    a[1][1]=a[2][2]=1;
    b[1][2]=1;
    b[2][1]=b[2][2]=1;
  f[1][1]=f[1][2]=1;
    for(i=0;(1<<i)<=k-1;++i)
    {
        if((1<<i)&&(k-1))
             {  aux[1][1]=a[1][1]; aux[1][2]=a[1][2]; aux[2][1]=a[2][1]; aux[2][2]=a[2][2];
                 a[1][1]=(aux[1][1]*b[1][1]+aux[1][2]*b[2][1])%p;
                 a[1][2]=(aux[1][1]*b[1][2]+aux[1][2]*b[2][2])%p;
                 a[2][1]=(aux[2][1]*b[1][1]+aux[2][2]*b[2][1])%p;
                 a[2][2]=(aux[2][1]*b[1][2]+aux[2][2]*b[2][2])%p;
             }
    aux[1][1]=b[1][1]; aux[1][2]=b[1][2]; aux[2][1]=b[2][1]; aux[2][2]=b[2][2];

    b[1][1]=(aux[1][1]*aux[1][1]+aux[1][2]*aux[2][1])%p;
    b[1][2]=(aux[1][1]*aux[1][2]+aux[1][2]*aux[2][2])%p;
    b[2][1]=(aux[2][1]*aux[1][1]+aux[2][2]*aux[2][1])%p;
    b[2][2]=(aux[2][1]*aux[1][2]+aux[2][2]*aux[2][2])%p;
    }
    aux[1][1]=f[1][1];
    aux[1][2]=f[1][2];
    f[1][1]=(aux[1][1]*b[1][1]+aux[1][2]*b[2][1])%p;
    f[1][2]=(aux[1][1]*b[1][2]+aux[1][2]*b[2][2])%p;
    fout<<f[1][1];


    return 0;
}