#include <iostream>
#include <fstream>

#define int long long

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

const int N = 2, mod = 666013;
int F[N][N] = {   {1, 1},
                  {1, 0}
              };
int ans[N][N] = {   {1, 0},
                    {0, 1}
                }; // element neutru la inmultirea de matrici

void produs(int p[N][N], int a[N][N], int b[N][N]){
    int aux[N][N];
    for(int i = 0; i < N; i++){
        for(int k = 0; k < N; k++){
            aux[i][k] = 0;
            for(int j = 0; j < N; j++)
                aux[i][k] = (aux[i][k] + a[i][j] * b[j][k] % mod) % mod;
        }
    }
    for(int i = 0; i < N; i++)
        for(int k = 0; k < N; k++)
            p[i][k] = aux[i][k];
}

void lgpow(int a[N][N], int pow){
    while(pow != 0){
        if(pow % 2 != 0) produs(a, a, F);
        produs(F, F, F);
        pow /= 2;
    }   
}

signed main(){
    int n;
    fin >> n;
    lgpow(ans, n - 1);
    fout << ans[0][0];
    return 0;
}

/*

    | 1 1 |   | fn - 1 |   | fn     |
    |     | x |        | = |        |
    | 1 0 |   | fn - 2 |   | fn - 1 |

    | 1 1 |   | fn - 2 |   | fn - 1 |
    |     | x |        | = |        |
    | 1 0 |   | fn - 3 |   | fn - 2 |

    deci

              | fn - 2 |   | fn     |
    F ^ 2   x |        | = |        |
              | fn - 3 |   | fn - 1 |

    aplicand aceasta strategie de n - 2 ori obtinem (progresie geometrica):

                  | f1 |   | fn     |
    F ^ (n - 1) x |    | = |        |
                  | f0 |   | fn - 1 |

    * matricea F se poate ridica la putere in timp logaritmic

*/