#include <bits/stdc++.h>

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

const long long MOD = 666013;
long long mat[3][3], t[2][3], sol[3][3], aux[3][3];

int main() {
    int k;
    in >> k;
    mat[1][2] = mat[2][1] = mat[2][2] = 1;
    t[1][1] = t[1][2] = 1;
    sol[1][1] = sol[2][2] = 1;
    k ++;
    while(k != 0) {
        if(k % 2 == 1) {
            memset(aux, 0, sizeof aux);
            for(int i = 1; i < 3; i ++)  // linie prima matrice
                for(int j = 1; j < 3; j ++) // coloana a doua matrice
                    for(int k = 1; k < 3; k ++)
                        aux[i][j] = (aux[i][j] + sol[i][k] * mat[k][j]) % MOD;
            for(int i = 1; i < 3; i ++)
                for(int j = 1; j < 3; j ++)
                    sol[i][j] = aux[i][j];
        }
        memset(aux, 0, sizeof aux);
        for(int i = 1; i < 3; i ++)
            for(int j = 1; j < 3; j ++)
                for(int k = 1; k < 3; k ++)
                    aux[i][j] = (aux[i][j] + mat[i][k] * mat[k][j]) % MOD;
        for(int i = 1; i < 3; i ++)
            for(int j = 1; j < 3; j ++)
                mat[i][j] = aux[i][j];
        k /= 2;
    }
    memset(aux, 0, sizeof aux);
    for(int i = 1; i < 3; i ++)
        for(int j = 1; j < 2; j ++)
            for(int k = 1; k < 3; k ++)
                aux[i][j] = (aux[i][j] + sol[i][k] * t[k][j]) % MOD;
    out << aux[1][1];
    return 0;
}