#include <fstream>
#include <vector>

using namespace std;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

vector <vector <int> > z(2),s(2);
int k,y;

void vxv(vector <vector <int> > &x,vector <vector <int> > y)
{
    vector <vector <int> > a(2);
    a[0].resize(2);
    a[1].resize(2);
    a[0][0]=(x[0][0]*y[0][0]+x[0][1]*y[1][0]) % 666013;
    a[0][1]=(x[0][0]*y[0][1]+x[0][1]*y[1][1]) % 666013;
    a[1][0]=(x[1][0]*y[0][0]+x[1][1]*y[1][0]) % 666013;
    a[1][1]=(x[1][0]*y[0][1]+x[1][1]*y[1][1]) % 666013;
    x=a;
}

void zsolve()
{
    for (int i=0,y=k-1; (1<<i)<=y; i++)
    {
        if ( ( (1<<i) & y)>0) vxv(s,z);
        vxv(z,z);
    }
}

main()
{
    cin >> k;
    if (k==0) { cout << 0 ; exit(0);}
    z[0].resize(2);
    z[1].resize(2);
    s=z;
    z[0][0]=0; z[0][1]=1;
    z[1][0]=1; z[1][1]=1;
    s[0][0]=1; s[0][1]=0;
    s[1][0]=0; s[1][1]=1;
    zsolve();
    cout << s[1][1];
}