#include <fstream>

using namespace std;
struct mat
{
    int a[2][2];
};
mat p,q;
int n,i,j,k;
mat inm(mat x, mat y)
{
    mat z;
    for(i=0; i<2; i++)
    for(j=0; j<2; j++)
    {
        z.a[i][j]=0;
        for(k=0; k<2; k++)
            z.a[i][j]+=x.a[i][k]*y.a[k][j];
        z.a[i][j]=z.a[i][j]%666013;
    }
    return z;
}
int main()
{
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    f>>n;
    n--;
    q.a[0][1]=0;
    q.a[0][1]=1;
    q.a[1][0]=1;
    q.a[1][1]=1;
    while(n%2==0)
    {
        q=inm(q,q);
        n/=2;
    }
    n/=2;
    p=q;
    q=inm(q,q);
    while(n)
    {
        if(n%2) p=inm(p,q);
        q=inm(q,q);
        n/=2;
    }
    g<<p.a[1][1]<<'\n';
    f.close(); g.close();
    return 0;
}