#include <iostream>
#include <fstream>
# define mod 666013
using namespace std;

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

struct filip
{
    long long x,numar,aux;
} mat[3][3];

long long i,j,numar,p,q;

void inmultestex()
{
    for(i = 1; i <= 2; i++)
        for(j = 1; j <= 2; j++)
            mat[i][j].aux = mat[i][j].x;
    for(i = 1; i <= 2; i++)
        for(j = 1; j <= 2; j++)
        {
            numar = 0;
            for(q = 1; q <= 2; q++)
                numar = (numar + (mat[i][q].aux * mat[q][j].aux)%mod) % mod;
            mat[i][j].x = numar;
        }
}

void inmultestenumar()
{
    for(i = 1; i <= 2; i++)
        for(j = 1; j <= 2; j++)
        {
            numar = 0;
            for(q = 1; q <= 2; q++)
                numar = ((numar + mat[i][q].x * mat[q][j].numar)%mod)% mod;
            mat[i][j].aux = numar;
        }
    for(i = 1; i <= 2; i++)
        for(j = 1; j <= 2; j++)
            mat[i][j].numar = mat[i][j].aux;
}

void afisare()
{
    for(i = 1; i <= 2; i++)
    {
        for(j = 1; j <= 2; j++)
            cout << mat[i][j].numar <<" ";
        cout<<endl;
    }
}

int main()
{
    f >> p;
    mat[1][2].x = mat[1][2].numar = 1;
    mat[2][2].x = mat[2][2].numar = 1;
    mat[2][1].x = mat[2][1].numar = 1;
    while(p)
    {
        if((p & 1))
        {
            inmultestenumar();
            p--;
        }
        else
        {
            inmultestex();
            p = (p >> 1);
        }
    }
    g << mat[1][1].numar;
    return 0;
}