#include <fstream>
#define MODULO 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
struct mat{long long int a11,a12,a21,a22;};
mat prod(mat x,mat y);
long long int n;
mat x,I;
mat ceva;
mat pow(mat  x,long long int n);
int main()
{
    x.a11=x.a12=x.a21=1;
    x.a22=0;
    I.a11=I.a22=1;

    fin>>n;
    ceva=pow(x,n);
    fout<<ceva.a12;


}
mat pow(mat  x,long long int n)
{
    if(!n)
        return I;
    if(n%2)
        return prod(x,pow(prod(x,x),n/2));
    else
        return pow(prod(x,x),n/2);
}
mat prod(mat x,mat y)
{
    mat rez;
    rez.a11=((x.a11*y.a11)%MODULO+(x.a12*y.a21)%MODULO)%MODULO;
    rez.a12=((x.a11*y.a12)%MODULO+(x.a12*y.a22)%MODULO)%MODULO;
    rez.a21=((x.a21*y.a11)%MODULO+(x.a22*y.a21)%MODULO)%MODULO;
    rez.a22=((x.a21*y.a12)%MODULO+(x.a22*y.a22)%MODULO)%MODULO;
    return rez;
}