#include <bits/stdc++.h>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define cin fin
#define cout fout
using ll = long long;
const ll mod = 666013;


int main()
{
    ll k;
    cin>>k;

    /// ans = matricea care va contine raspunsul final
    /// O initializam ca fiind matricea unitate
    ll ans[2][2];
    ans[0][0] = ans[1][1] = 1;
    ans[0][1] = ans[1][0] = 0;

    /// mat = matricea [[0, 1], [1, 1]] aceasta reprezinta matricea cu care trebuie sa inmultim pentru a afla urmatorul termen fibonnaci
    ll mat[2][2];
    mat[0][0] = 0;
    mat[0][1] = mat[1][0] = mat[1][1] = 1;


    //cout<<ans[0][0] <<" "<<ans[0][1]<<'\n'<<ans[1][0]<<" "<<ans[1][1]<<"\n\n";
    //cout<<mat[0][0] <<" "<<mat[0][1]<<'\n'<<mat[1][0]<<" "<<mat[1][1]<<'\n';

    ll aux[2][2];

    /// Ne folosim de algoritmul de exponentiere rapida
    /// ans = 1 devine ans = matricea unitate
    k--;
    while(k){
      if(k % 2 != 0){
        /// Algoritmul de inmultire a matricelor.
        /// Acesta poate fi realizat si cu ajutorul a 4 for-uri, dar in cazul matricelor 2x2 aceasta forma este mai simpla
        /// Aceste inmultiri reprezinta ans = ans * mat
        /// Atentie! Este important sa folosim varibilele (sau o matrice) auxiliare, deoarce, valoarea ans[0][0] este folosita in mai multe calcule,
        /// iar daca am actualiza instant valoarea ei, aceasta ar folosi noua valoare in viitoarele calcule, cauzand rezultate eronate!
        ll a = ((ans[0][0] * mat[0][0]) % mod + (ans[0][1] * mat[1][0]) % mod) % mod;
        ll b = ((ans[0][0] * mat[0][1]) % mod + (ans[0][1] * mat[1][1]) % mod) % mod;
        ll c = ((ans[1][0] * mat[0][0]) % mod + (ans[1][1] * mat[1][0]) % mod) % mod;
        ll d = ((ans[1][0] * mat[0][1]) % mod + (ans[1][1] * mat[1][1]) % mod) % mod;
        ans[0][0] = a;
        ans[0][1] = b;
        ans[1][0] = c;
        ans[1][1] = d;
        k--;
      }
      else{
        /// Aceste inmultiri reprezinta mat = mat * mat
        ll a = ((mat[0][0] * mat[0][0]) % mod + (mat[0][1] * mat[1][0]) % mod) % mod;
        ll b = ((mat[0][0] * mat[0][1]) % mod + (mat[0][1] * mat[1][1]) % mod) % mod;
        ll c = ((mat[1][0] * mat[0][0]) % mod + (mat[1][1] * mat[1][0]) % mod) % mod;
        ll d = ((mat[1][0] * mat[0][1]) % mod + (mat[1][1] * mat[1][1]) % mod) % mod;
        mat[0][0] = a;
        mat[0][1] = b;
        mat[1][0] = c;
        mat[1][1] = d;
        k /= 2;
      }
    }

    //cout<<ans[0][0] <<" "<<ans[0][1]<<'\n'<<ans[1][0]<<" "<<ans[1][1]<<'\n';
    cout<<ans[1][1]<<'\n';
    return 0;
}