#include <iostream>
#include <fstream>
#define MOD 666013

using namespace std;

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

long long mat1[3][3]
{
    0, 0, 0,
    0, 0, 1,
    0, 1, 1,
};
long long mat2[3][3];

void cpymat(long long a[][3], long long b[][3])
{
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            a[i][j]=b[i][j];
}

void timesmat(long long a[][3], long long b[][3])
{
    long long auxmat[3][3]{0, 0, 0, 0, 0, 0, 0, 0, 0};
    for(int i=1; i<3; i++)
        for(int j=1; j<3; j++)
            for(int k=1; k<3; k++)
                auxmat[i][j]+=(a[i][k]*b[k][j]), auxmat[i][j]%=MOD;
    cpymat(a, auxmat);
}

void poww(int b)
{
    if(b==0) return;
    if(b==1) return;
    poww(b/2);
    if(b%2) timesmat(mat1, mat1), timesmat(mat1, mat2);
    else timesmat(mat1, mat1);
}

int main()
{
    cpymat(mat2, mat1);
    int n;
    in>>n;
    poww(n-1), out<<mat1[2][2];
    return 0;
}