#include <fstream>
using namespace std;

ifstream cin ("kfib.in");
ofstream cout ("kfib.out");

int main() {
    long long a11=1,a12=0,a21=0,a22=1,b11,b12,b21,b22,p11=1,p12=1,p21=1,p22=0,mod=666013;
    cin>>k;
	while (k) {
		if (k%2==1) {
			b11=(a11*p11+a12*p21)%mod;
			b12=(a11*p12+a12*p22)%mod;
			b21=(a21*p11+a22*p21)%mod;
			b22=(a21*p12+a22*p22)%mod;
			a11=b11;a12=b12;a21=b21;a22=b22;
		}
		b11=(p11*p11+p12*p21)%mod;
		b12=(p11*p12+p12*p22)%mod;
		b21=(p21*p11+p22*p21)%mod;
		b22=(p21*p12+p22*p22)%mod;
		p11=b11;p12=b12;p21=b21;p22=b22;
		k/=2;
	}
	cout<<a12;
}