/*

    cod facut de AndreiG

*/
#include <fstream>
#pragma GCC optimize("O3,unroll-loops")
#include <algorithm>
#include <cstring>
#include <climits>
#include <iomanip>
#include <numeric>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#define int long long
//#define int short
#define pb push_back
#define f first
#define s second
using namespace std;
 
ifstream cin("kfib.in");
ofstream cout("kfib.out");
 
const int nmax = 1e9;
const int mod = 666013;
 
int n;
 
struct Matrice{
    int m[2][2];
 
    Matrice operator*(const Matrice& a) const{
        Matrice b = {0};
        for (int i = 0; i < 2; i++){
            for (int j = 0; j < 2; j++){
                for (int k = 0; k < 2; k++){
                    b.m[i][j] += m[i][k] * a.m[k][j];
                    b.m[i][j] %= mod;
                }
            }
        }
        return b;
    }
};
 
Matrice MatriceZero = {1, 0, 0, 1};
Matrice MatriceFib = {0, 1, 1, 1};
Matrice MatriceFibStart = {0, 1, 0, 0};
 
Matrice ex(Matrice a, int p){
    if (p == 0){
        return MatriceZero;
    }
    if (p % 2){
        return a * ex(a, p - 1);
    }
    Matrice idk = ex(a, p / 2);
    return idk * idk;
}
 
void fastio(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}
 
void handleinput(){
    cin>>n;
}
 
void handleoutput(){
    if (!n){
        cout<<0;
        return;
    }
    Matrice idk = MatriceFibStart * ex(MatriceFib, n - 1);
    cout<<idk.m[0][1];
}
 
signed main(){
    fastio();
    handleinput();
    handleoutput();
}