#include <fstream>
#include <cstring>
using namespace std;

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

int k,a[3][3];

void aduna(int A[][3], int B[][3], int C[][3]) {
    int i, j, k;
    for (i = 1; i <= 2; i++)
        for (j = 1; j <= 2; j++)
            for (k = 1; k <= 2; k++)
                C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % 666013;
}

void logpow()
{
    int p[3][3],aux[3][3];

    p[1][1] = 0;
    p[1][2] = p[2][1] = p[2][2] = 1;

    a[1][1]=1;
    a[1][2]=1;

    for(int d=0; (1<<d) <= k; d++)
    {
        if((1<<d)&k)
        {
            for (int i = 1; i <= 2; i++)
                for (int j = 1; j <= 2; j++)
                    aux[i][j] = 0;
                aduna(p,a,aux);
            for (int i = 1; i <= 2; i++)
                for (int j = 1; j <= 2; j++)
                    a[i][j]=aux[i][j];
        }
        for (int i = 1; i <= 2; i++)
                for (int j = 1; j <= 2; j++)
                    aux[i][j] = 0;
        aduna(p,p,aux);
        for (int i = 1; i <= 2; i++)
                for (int j = 1; j <= 2; j++)
                    p[i][j] = aux[i][j];
    }
}

int main()
{
    f>>k;
    k++;
    logpow();
    g<<a[1][1];
    return 0;
}