#include <bits/stdc++.h>
#define ll long long
#define pb push_back
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;
        }
    }
    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;
    for(int i=0;(1<<i)<=n;i++){
        if(n&(1<<i)) fib=fib*AUX;
        AUX=AUX*AUX;
    }
    cout << fib.arr[1][1];
}