#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define int long long
using namespace std;

const int mod=666013;

struct mat{
    int rows,cols;
    int arr[105][105];
};

mat operator*(mat a,mat b){
    mat c;
    c.rows=a.rows;
    c.cols=b.cols;
    for(int i=1;i<=c.rows;i++) for(int j=1;j<=c.cols;j++) c.arr[i][j]=0;
    for(int i=1;i<=c.rows;i++){
        for(int j=1;j<=c.cols;j++){
            for(int t=1;t<=a.cols;t++) c.arr[i][j]=(c.arr[i][j]+(a.arr[i][t]*b.arr[t][j])%mod)%mod;
        }
    }
    return c;
}

int n;

int32_t main() {
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    cin >> n;
    mat fib;
    fib.rows=1;
    fib.cols=2;
    fib.arr[1][1]=0;
    fib.arr[1][2]=1;
    mat AUX;
    AUX.rows=2;
    AUX.cols=2;
    AUX.arr[1][1]=0;
    AUX.arr[1][2]=1;
    AUX.arr[2][1]=1;
    AUX.arr[2][2]=1;
    mat leru=AUX;
    for(int i=0LL;(1LL<<i)<=(n-1LL);i++){
        if(((n-1LL)&(1LL<<i))>=1LL) AUX=AUX*leru;
        leru=leru*leru;
    }
   // cout << "CHECK" << ' ' << AUX.arr[1][1] << ' ' << AUX.arr[1][2] << ' ' << AUX.arr[2][1] << ' ' << AUX.arr[2][2] << '\n';
    fib=fib*AUX;
    cout << fib.arr[1][1];
}