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

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

long long int INIT[2][2]={{0, 1}, {1, 1}}, FINMAT[2][2]={{1, 0}, {0, 1}};
long long int n;


void multiply(long long int A[2][2], long long int B[2][2])
{
    long long int aux;
    long long int C[2][2];
    aux=A[0][0]*B[0][0]+A[0][1]*B[1][0];
    C[0][0]=aux%MODULO;
    aux=A[0][0]*B[0][1]+A[0][1]*B[1][1];
    C[0][1]=aux%MODULO;
    aux=A[1][0]*B[0][0]+A[1][1]*B[0][1];
    C[1][0]=aux%MODULO;
    aux=A[1][0]*B[0][1]+A[1][1]*B[1][1];
    C[1][1]=aux%MODULO;

    for (int i=0;i<2;i++)
        for (int j=0;j<2;j++)
            A[i][j]=C[i][j];
}

int main()
{
    fin>>n;
    n++;
    while (n>1)
    {
        if (n%2==0)
        {
            n/=2;
            multiply(INIT, INIT);
        }
        else
        {
            n--;
            multiply(FINMAT, INIT);
        }
    }
    multiply(INIT, FINMAT);

    fout<<INIT[0][0];

    return 0;
}