#include <fstream>

using namespace std;
const long c = 666013;

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

void produs (int a[2][2], int b[2][2], int p[2][2])
{
    int aux [2][2];
    aux[0][0]=a[0][0]*b[0][0]+a[0][0]*b[1][0];
    aux[0][1]=a[0][0]*b[0][1]+a[0][1]*b[1][1];
    aux[1][0]=a[1][0]*b[0][0]+a[1][1]*b[1][0];
    aux[1][1]=a[1][1]*b[0][1]+a[1][1]*b[1][1];
    p[0][0]=(aux[0][0])%c;
    p[0][1]=(aux[0][1])%c;
    p[1][0]=(aux[1][0])%c;
    p[1][1]=(aux[1][1])%c;
}
void putere (int a[2][2], int n, int p[2][2])
{
    if (n==1)
    {
        p[0][0]=a[0][0];
        p[0][1]=a[0][1];
        p[1][0]=a[1][0];
        p[1][1]=a[1][1];
        return ;
    }
    if (n%2==1)
        produs (a, p, p);
    produs (a, a, a);
    putere (a, n/2, p);
}

int main()
{
    int n;
    in >> n;
    out << putere(n);
        return 0;
}