#include<fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int MODULE = 666013;

int n, fib[2][2] = {0, 1,
                    1, 1};

inline void matrixProduct(int matrix1[2][2], int matrix2[2][2]){

    int ans[2][2] = {0};

    int m, n, p;
    for(m = 0; m < 2; ++m)
        for(n = 0; n < 2; ++n)
            for(p = 0; p < 2; ++p)
                ans[m][n] += (1LL * matrix1[m][p] * matrix2[p][n]) % MODULE;

    matrix1[0][0] = ans[0][0];
    matrix1[0][1] = ans[0][1];
    matrix1[1][0] = ans[1][0];
    matrix1[1][1] = ans[1][1];
}

inline int nthFibonacci(){

    int exponent, ans[2][2] = {1, 0,
                               0, 1};
    for(exponent = n - 1; exponent; exponent >>=1){

        if(exponent & 1)
            matrixProduct(ans, fib);
        matrixProduct(fib, fib);
    }

    return ans[1][1] % MODULE;
}
int main(){

    fin >> n;
    fout << nthFibonacci();
}