#include <fstream>
#define MOD 666013

using namespace std;

long long int ceva[3][3],rez[3][3],ans[2];
int n,i,j;

void inmultire(long long int a[3][3],long long int b[3][3])
{
    rez[1][1]=((a[1][1]%MOD*b[1][1]%MOD)%MOD+(a[1][2]%MOD*b[2][1]%MOD)%MOD)%MOD;
    rez[1][2]=((a[1][1]%MOD*b[1][2]%MOD)%MOD+(a[1][2]%MOD*b[2][2]%MOD)%MOD)%MOD;
    rez[2][1]=((a[2][1]%MOD*b[1][1]%MOD)%MOD+(a[2][2]%MOD*b[2][1]%MOD)%MOD)%MOD;
    rez[2][2]=((a[2][1]%MOD*b[1][2]%MOD)%MOD+(a[2][2]%MOD*b[2][2]%MOD)%MOD)%MOD;
}

void putere(long long int baza[3][3], int exp)
{
    long long int sol[3][3];

    sol[1][1]=1;
    sol[1][2]=0;
    sol[2][1]=0;
    sol[2][2]=1;

    for(;exp;exp>>=1)
    {
        if((exp&1)==1)
        {
            inmultire(sol,baza);
            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)
                    sol[i][j]=rez[i][j];
        }
        inmultire(baza,baza);
            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)
                    baza[i][j]=rez[i][j];


    }
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
            ceva[i][j]=sol[i][j]%MOD;
}

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

    ceva[1][1]=0;
    ceva[1][2]=1;
    ceva[2][1]=1;
    ceva[2][2]=1;

    f>>n;

    putere(ceva,n-1);

    ans[1]=(1*ceva[1][1]%MOD+1*ceva[1][2]%MOD)%MOD;
    ans[2]=(1*ceva[2][1]%MOD+1*ceva[2][2]%MOD)%MOD;
    g<<ans[1];
}