#include <iostream>
#include <fstream>
using namespace std;
long long x[3][3];
long long p[3][3];

void produs( long long a[3][3], long long b[3][3])
{
    int i,j,k;
    long long aux[3][3];
    for(i=0; i<3; i++)
        for(j=0; j<3; j++)
        {
            aux[i][j]=0;
            for(k=0; k<3; k++)
                aux[i][j]+=a[i][k]*b[k][j];
        }
    for(i=0; i<3; i++)
        for(j=0; j<3; j++)
            a[i][j]=aux[i][j]%666013;

}



int main()
{
    int k;
    x[0][0]=x[0][1]=x[1][0]=x[2][1]=1;
    p[0][0]=p[1][1]=p[2][2]=1;
    ifstream in("kfib.in");
    in>>k;
    k--;
    k--;

    while(k!=0)
    {
        if(k%2!=0) produs(p,x);
        produs(x,x);
        k/=2;
    }
    ofstream out("kfib.out");
    out<<(p[0][1]+p[0][0])%666013;

    return 0;
}