#include <fstream>
#define MOD 666013
using namespace std;

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

int K;
int Z[3][3],M1[3][3],Sol[3][3];


void Multiply(int A[3][3],int B[3][3])
{
    int C[3][3];
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            C[i][j] = 0;

    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                C[i][j]=(C[i][j] + (1LL*A[i][k]*B[k][j]))%MOD;

    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            B[i][j] = C[i][j];
}
void LogPow(int M[3][3], int P)
{
    while(P)
    {
        if(P&1)
            Multiply(M,Sol);
        Multiply(M,M);
        P = P >> 1;
    }
}


int main()
{
    fin>>K;

    Z[0][1]=Z[1][0]=Z[1][1] = 1;

    M1[0][0]=0; M1[0][1] = 1;

    LogPow(Z,K-1);

    Multiply(M1,Sol);

    fout<<Z[0][0]<<"\n";

    return 0;
}