#include <fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");
#define LL long long
LL a = 0, b = 1, c = 1, d = 1;
LL r1 = 1, r2 = 0, r3 = 0, r4 = 1;
LL aux1, aux2, aux3, aux4;
LL solve(int k){
    k--;
    while(k){
        if(k % 2 == 0){
            k /= 2;
            aux1 = a*a + b*c;
            aux2 = b*a + d*b;
            aux3 = a*c + c*d;
            aux4 = b*c + d*d;
            a = aux1 % 666013;
            b = aux2 % 666013;
            c = aux3 % 666013;
            d = aux4 % 666013;
        }
        else {
            --k;
            aux1 = r1*a + r2*b;
            aux2 = r1*b + r2*d;
            aux3 = r3*a + r4*c;
            aux4 = r3*b + r4*d;
            r1 = aux1 % 666013;
            r2 = aux2 % 666013;
            r3 = aux3 % 666013;
            r4 = aux4 % 666013;
        }
    }
    return r4;
}

int main()
{
    int k;
    f >> k;
    if(!k) g<< 0;
    else
    g << solve(k);
    return 0;
}