#include <fstream>

using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int a[2][2],sol[2][2],rez[2][2];
void inmultire()
{
    rez[0][0]=(a[0][0]*sol[0][0]+a[0][1]*sol[1][0])%666013;
    rez[0][1]=(a[0][0]*sol[0][1]+a[0][1]*sol[1][1])%666013;
    rez[1][0]=(a[1][0]*sol[0][0]+a[1][1]*sol[1][0])%666013;
    rez[1][1]=(a[1][0]*sol[0][1]+a[1][1]*sol[1][1])%666013;
    sol[0][0]=rez[0][0];
    sol[0][1]=rez[0][1];
    sol[1][0]=rez[1][0];
    sol[1][1]=rez[1][1];
}
int main()
{
   long long int k;
    f>>k;
    f.close();
    a[0][0]=sol[0][0]=0;
    a[0][1]=1;
    a[1][0]=a[1][1]=sol[0][1]=sol[1][0]=sol[1][1]=1;
    for(int i=1;i<k-1;i++)
        inmultire();
    g<<sol[1][1];

}