#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");

const int NMax = 1e5 + 5;
const int mod = 666013;

int K;

struct matrice22 {
    int a[3][3];
    matrice22() {}
    matrice22(int x) {
        if (x == 0) {
            for (int i=1;i<=2;++i) {
                for (int j=1;j<=2;++j) {
                    a[i][j] = 0;
                }
            }
        }
        else if (x == 1) {
            for (int i=1;i<=2;++i) {
                for (int j=1;j<=2;++j) {
                    a[i][j] = 0;
                }
                a[i][i] = 1;
            }
        }
        else if (x == 10) {
            for (int i=1;i<=2;++i) {
                for (int j=1;j<=2;++j) {
                    a[i][j] = 1;
                }
            }
            a[1][1] = 0;
        }
    }
};

struct matrice21 {
    int v[3];
    matrice21() {}
    matrice21(int x) {
        if (x == 0) {
            for (int i=1;i<=2;++i) {
                v[i] = 0;
            }
        }
    }
};

matrice22 prod(matrice22,matrice22);
matrice21 prod(matrice22,matrice21);
matrice22 pw(matrice22,int);

int main() {
    in>>K;

    matrice22 A(10);
    A = pw(A,K);

    matrice21 B;
    B.v[1] = 0;
    B.v[2] = 1;

    matrice21 result = prod(A,B);
    out<<result.v[1]<<'\n';

    return 0;
}

matrice22 pw(matrice22 A,int e) {
    matrice22 res(1);
    while (e>0) {
        if (e % 2 == 1) {
            res = prod(res,A);
        }
        A = prod(A,A);
        e >>= 1;
    }
    return res;
}

matrice22 prod(matrice22 X,matrice22 Y) {
    matrice22 res(0);

    for (int i=1;i<=2;++i) {
        for (int j=1;j<=2;++j) {
            for (int k=1;k<=2;++k) {
                res.a[i][j] = (res.a[i][j] + 1LL * X.a[i][k] * Y.a[k][j]) % mod;
            }
        }
    }
    return res;
}

matrice21 prod(matrice22 X,matrice21 Y) {
    matrice21 res(0);
    for (int i=1;i<=2;++i) {
        for (int j=1;j<=2;++j) {
            res.v[i] = (res.v[i] + 1LL * X.a[i][j] * Y.v[j]) % mod;
        }
    }
    return res;
}