/*#include <fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");


int main()
{
    int m,a,b,aux;
    f>>m;

    a=1;
    b=1;

    for(int i=3;i<=m;++i)
        {
        aux=a+b;
        a=b%666013;
        b=aux%666013;
        }
    g<<b;
    return 0;
}
*/
#include <fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

long long a[5],z[5],p[5];//2707124

void inm_matr(long long a[],long long p[])
{
    a[1]=(p[1]*z[1]+p[2]*z[3])%666013;
    a[2]=(p[1]*z[2]+p[2]*z[4])%666013;
    a[3]=(p[3]*z[1]+p[4]*z[3])%666013;
    a[4]=(p[3]*z[2]+p[4]*z[4])%666013;

    for(int i=1;i<=4;++i)
        p[i]=a[i];
}

void rid_la_putere_matr(long long z[],int n)
{
    while(n)
        {
        if(n%2)
            {
            inm_matr(a,p);;
            n--;
            }
        inm_matr(a,z);
        n/=2;
        }
}

int main()
{
    int n;
    f>>n;
    n--;

    p[1]=1;      z[1]=0;
    p[2]=0;      z[2]=1;
    p[3]=0;      z[3]=1;
    p[4]=1;      z[4]=1;

    rid_la_putere_matr(z,n);

    g<<p[4]%666013;

    return 0;
}