#include <iostream>
#include <fstream>

using namespace std;

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

int N;

void inm(int n,long long a[5][5],long long b[5][5])
{
    int c[5][5];
    c[1][1]=c[1][2]=c[2][1]=c[2][2]=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            for(int p=1; p<=n; p++)
            {
                c[i][j]=(c[i][j]+(a[i][p]*b[p][j]))%666013;
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            a[i][j]=c[i][j];
        }

    }

}

void pw(long long base[5][5],long long p)
{
    long long sol[5][5];
    sol[1][1]=sol[2][2]=1;
    sol[1][2]=sol[2][1]=0;

    while(p>0)
    {
        if(p%2==0)
        {
            inm(2,base,base);

            p/=2;
        }
        else
        {
            inm(2,sol,base);
            p--;
        }
    }

    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=2; j++)
        {
            base[i][j]=sol[i][j];
        }
    }
}

int main()
{
    long long baza[5][5];
    in>>N;
    baza[1][1]=baza[1][2]=baza[2][1]=1;
    baza[2][2]=0;

    pw(baza,N);
    out<<baza[1][2];
}