#include <iostream>
#include <fstream>
using namespace std;

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

long long m[2][2], rsp[2][2], n;

void inmultire(long long a[2][2], long long b[2][2]) {
    long long c[2][2];
    c[0][0] = a[0][0];
    c[1][0] = a[1][0];
    c[0][1] = a[0][1];
    c[1][1] = a[1][1];

    long long d[2][2];
    d[0][0] = b[0][0];
    d[1][0] = b[1][0];
    d[0][1] = b[0][1];
    d[1][1] = b[1][1];

    a[0][0] = (c[0][0] * d[0][0] + c[0][1] * d[1][0])%666013;
    a[0][1] = (c[0][0] * d[0][1] + c[0][1] * d[1][1])%666013;
    a[1][0] = (c[1][0] * d[0][0] + c[1][1] * d[1][0])%666013;
    a[1][1] = (c[1][0] * d[0][1] + c[1][1] * d[1][1])%666013;
}

void ridicare(int n) {
    while(n > 0) {
        if(n % 2 == 1)
            inmultire(rsp, m);
        inmultire(m, m);
        n /= 2;
    }
}

int main()
{

    f >> n;

    m[0][0] = 1;
    m[1][0] = 1;
    m[0][1] = 1;
    m[1][1] = 0;

    rsp[0][0] = 1;
    rsp[1][0] = 0;
    rsp[0][1] = 0;
    rsp[1][1] = 1;

    ridicare(n);

    g << rsp[0][1];
    return 0;
}