#include <iostream>
#include <fstream>
#define nmax 1000000005
#define mod 666013
#define ll long long
using namespace std;

struct Matrix {
	ll x, y, z, t;
};

Matrix attrib(ll a, ll b, ll c, ll d) {
	Matrix A;
	A.x = a;
	A.y = b;
	A.z = c;
	A.t = d;
	return A;
}

Matrix product(Matrix A, Matrix B) {
    return attrib((A.x*B.x + A.y*B.z)%mod, (A.x*B.y + A.y*B.t)%mod, (A.z*B.x + A.t*B.z)%mod, (A.z*B.y + A.t*B.t)%mod);
}

Matrix power(Matrix A, int exp) {
    if(exp == 1) return A;

    Matrix half = power(A, exp/2);

    if(exp % 2 == 0) return product(half, half);
    return product(product(half, half), A);
}

//void printMatrix(Matrix A) { cout<<"("<<A.x<<" "<<A.y<<")\n("<<A.z<<" "<<A.t<<")\n"; }

int n;

int main() {
	ifstream f("kfib.in");
	ofstream g("kfib.out");

    f>>n;
    g<<power(attrib(0, 1, 1, 1), n).z<<"\n";


    return 0;
}