//#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define vvi vector<vector<int> >
const int mod = 666013;
vvi i2 = {{1, 0}, {0, 1}};

vvi prod(vvi a, vvi b) {

	vvi rasp;
	for(int i=0;i<a.size();i++){
        rasp.push_back({});
        for(int j=0;j<b[0].size();j++){
            rasp[i].push_back(0);
        }
	}
	for(int i=0;i<a.size();i++){
        for(int j=0;j<b[0].size();j++){
            for(int k=0;k<b.size();k++){
                rasp[i][j]+=(1LL*a[i][k]*b[k][j]%mod);
                rasp[i][j]%=mod;
            }
        }
	}
	return rasp;
}

vvi putlog(vvi n, int k) {
	if(k==0)
        return i2;
    vvi x=putlog(n,k/2);
	if(k%2==0)
        return prod(x,x);
	return prod(prod(x,x),n);
}

int main() {
	ifstream cin("kfib.in");
	ofstream cout("kfib.out");
	int n;
	cin>>n;
	vvi mat={{0,1},{1,1}},ans={{0,1}};
	mat=putlog(mat,n-1);
	ans=prod(ans,mat);
	cout<<ans[0][1];;
}