#include <iostream>
#include <fstream>

using namespace std;

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

const int MOD=666013;
int a[2][2]={{0, 1},{0, 0}}; //matricea cu f(0) si f(1) pe prima linie
int c[2][2]={{0, 1},{1, 1}};
int sol[2][2]={{1, 0}, {0, 1}}; //matricea unitate

void inmultire(int a[2][2], int b[2][2])
{
    int c[2][2];
    int i, j, k;
    for(i=0; i<=1; i++)
    {
        for(j=0; j<=1; j++)
        {
            c[i][j]=0;
            for(k=0; k<=1; k++) c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%MOD;
        }
    }
    for(i=0; i<=1; i++) for(j=0; j<=1; j++) a[i][j]=c[i][j];
}

void putere(int sol[2][2], int k)
{
    while(k)
    {
        if(k%2==1)
        {
            inmultire(sol, c); k--;
        }
        else
        {
            inmultire(c, c);
            k=k/2;
        }
    }
}

int main()
{
    int n;
    fin>>n;
    putere(sol, n);
    inmultire(a, sol);
    fout<<a[0][0];
    return 0;
}