#include <bits/stdc++.h>
using namespace std;

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

#define cin fin
#define cout fout
/*
*/

const int NMAX=100;
const int MOD=666013;
int matr[NMAX][NMAX]=
{
    {0, 0, 0},
    {0, 0, 1},
    {0, 1, 1},
};
int m2[NMAX][NMAX]=
{
    {0, 0, 0},
    {0, 1, 0},
};
int v[4][NMAX][NMAX];
int n, s;


void atribuie(int n, int m, int v[NMAX][NMAX], int in[NMAX][NMAX])
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            in[i][j]=v[i][j];
}

void inm(int n, int m, int n2, int v[NMAX][NMAX], int v2[NMAX][NMAX], int rez[NMAX][NMAX])
{
    int aux[NMAX][NMAX];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n2; j++)
            aux[i][j]=0;
    for(int i=1; i<=n; i++)
        for(int q=1; q<=n2; q++)
            for(int j=1; j<=m; j++)
            {
                aux[i][q]+=((long long)v[i][j]*v2[j][q])%MOD;
                aux[i][q]%=MOD;
            }
    atribuie(n, n2, aux, rez);
}

void ridic_matr_put(int n, int v[NMAX][NMAX], int putere, int rez[NMAX][NMAX])
{
    int aux[NMAX][NMAX];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            aux[i][j]=0;
    if(putere==1)
    {
        atribuie(n, n, v, rez);
        return;
    }
    if(putere==0)
    {
        for(int i=1; i<=n; i++)
            aux[i][i]=1;
        atribuie(n, n, aux, rez);
        return;
    }
    ridic_matr_put(n, v, putere/2, aux);
    inm(n, n, n, aux, aux, aux);
    if(putere%2==1)
        inm(n, n, n, aux, v, aux);
    atribuie(n, n, aux, rez);
}

void afisare(int n, int m, int v[NMAX][NMAX])
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
            cout<<v[i][j]<<" ";
        cout<<"\n";
    }
}


int main()
{
    cin>>n;
    if(n==0)
        cout<<0;
    else
    if(n==1)
        cout<<1;
    else
    {
        ridic_matr_put(2, matr, n-1, matr);
        inm(1, 2, 2, m2, matr, m2);

        s+=m2[1][1]+m2[1][2];
        s%=MOD;
        cout<<s;
    }




    return 0;
}