#include <iostream>
#include <fstream>

#define MOD 666013

using namespace std;

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

unsigned long long a[2][2], c[2][2], r[2][2];

void init() {
    a[0][0]=r[0][0]=1;
    a[0][1]=r[0][1]=1;
    a[1][0]=r[1][0]=1;
    a[1][1]=r[1][1]=0;
}

void matrixMultiplication(unsigned long long x[2][2], unsigned long long y[2][2], unsigned long long z[2][2]) {
    z[0][0]=((x[0][0]*y[0][0])%MOD+(x[0][1]*y[1][0])%MOD)%MOD;
    z[0][1]=((x[0][0]*y[0][1])%MOD+(x[0][1]*y[1][1])%MOD)%MOD;
    z[1][0]=((x[1][0]*y[0][0])%MOD+(x[1][1]*y[1][0])%MOD)%MOD;
    z[1][1]=((x[1][0]*y[0][1])%MOD+(x[1][1]*y[1][1])%MOD)%MOD;
}

void matrixCopy(unsigned long long x[2][2], unsigned long long y[2][2]) {
    x[0][0]=y[0][0];
    x[0][1]=y[0][1];
    x[1][0]=y[1][0];
    x[1][1]=y[1][1];
}

void power(int k) {
    if (k==1 || k==2) {
        fout<<"1";
        return;
    }
    int n=k-2;
    while (n) {
        if (n%2==0) {
            matrixMultiplication(a, a, c);
            matrixCopy(a, c);
            n/=2;
        } else {
            matrixMultiplication(r, a, c);
            matrixCopy(r, c);
            n--;
        }
    }
}

int main() {
    int k;
    fin>>k;
    init();
    power(k);
    fout<<r[0][0];
    return 0;
}