#include <fstream>
#define MOD 666013
using namespace std;

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

long long a[5][5], b[5][5], c[5][5], sol[5][5];

void inmultire_matrice(long long a[5][5],long long b[5][5]) {
    long long s;
    for (int i = 1; i <= 2; i++)
        for (int j = 1; j <= 2; j++) {
            s=0;
            for (int k = 1; k <= 2; k++)
                s += a[i][k] * b[k][j];
            c[i][j] = s % MOD;
        }
    for (int i = 1; i <= 2; i++)
        for(int j = 1; j <= 2; j++)
            a[i][j] = c[i][j];
}

void ridicare_la_putere_log(long long p) {
    for (int i = 1; i <= 2; i++)
        for (int j = 1; j <= 2; j++)
            sol[i][j] = b[i][j];
    while(p != 0) {
        if (p % 2 == 1)
            inmultire_matrice(sol, b);
        inmultire_matrice(b, b);
        p /= 2;
    }
}

int main() {
    long long n;
    if (n == 0) {
        g << 0;
        return 0;
    }

    a[1][2] = 1;
    b[1][2] = 1;
    b[2][1] = 1;
    b[2][2] = 1;
    ridicare_la_putere_log(n-1);
    inmultire_matrice(a, sol);
    g << a[1][1];

    return 0;
}