#include <bits/stdc++.h>

#define MOD 666013
#define ll  long long

std::ifstream InFile("kfib.in");
std::ofstream OutFile("kfib.out");

int N;
struct MatrixStruct {
    MatrixStruct(ll a = 1, ll b = 0, ll c = 0, ll d = 1) {
        this->a = a;
        this->b = b;
        this->c = c;
        this->d = d;
    }
    ll a, b, c, d;
}   Matrix(0, 1, 1, 1);

ll a1, a2, b1, b2, c1, c2, d1, d2;
MatrixStruct operator * (MatrixStruct Matrix, const MatrixStruct& A) {
    a1 = Matrix.a; a2 = A.a;
    b1 = Matrix.b; b2 = A.b;
    c1 = Matrix.c; c2 = A.c;
    d1 = Matrix.d; d2 = A.d;
    Matrix.a = (a1*a2 % MOD + b1*c2 % MOD) % MOD;
    Matrix.b = (a1*b2 % MOD + b1*d2 % MOD) % MOD;
    Matrix.c = (c1*a2 % MOD + d1*c2 % MOD) % MOD;
    Matrix.d = (c1*b2 % MOD + d1*d2 % MOD) % MOD;
    return Matrix;
}

MatrixStruct Aux;
MatrixStruct Pow(int Exp) {
    if(Exp==0) return MatrixStruct(1, 0, 0, 1);

    Aux = Pow(Exp/2);
    if(Exp%2) return Aux*Aux*Matrix;
    return Aux*Aux;
}

void Citire() {
    InFile >> N;
}

void Rezolvare() {
    OutFile << Pow(N).b;
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}