//https://dmoj.ca/problem/fibonacci2
#include<iostream>
#include<vector>
#include<assert.h>
#include<fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
//long long m = 1000000007;
long long m = 666013;
inline vector<vector<long long>> matrix(int row, int col) {
	vector<vector<long long>> ret;
	ret.reserve(row);
	for (int i = 0; i < row; i++)
		ret.push_back(vector<long long>(col));
	return ret;
}
vector<vector<long long>> mul(vector<vector<long long>>& a, vector<vector<long long>>& b) {
	int N = a.size(), M = b.size(), K = b[0].size();
	assert(a[0].size() == (size_t)M); //if a=mat(m,n) & b=mat(p,q) a*b is imp if  n!=p
	vector<vector<long long>> ret = matrix(N, K);
	for (int i = 0; i < N; i++)
		for (int j = 0; j < K; j++)
			for (int k = 0; k < M; k++)
				ret[i][j] = (ret[i][j] + a[i][k] * b[k][j]) % m;
	return ret;
}
string n;
vector<vector<long long>> init = { {0,1} }, fib_m = { {1,1},{1,0} };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	fin >> n;
	if (n == "0")
		fout << 0 << endl;
	else if (n == "1")
		fout << 1 << endl;
	else {
		//raises the fibo matrix to n by considering each digit
		vector<vector<long long>> finalmult = { {1,0},{0,1} }, power = fib_m;
		for (int i = n.length() - 1; i >= 0; i--) {
			int cif = n[i] - '0';
			for (int j = 0; j < cif; j++)
				finalmult = mul(finalmult, power);
			vector<vector<long long>> new_power = { {1,0},{0,1} };
			for (int j = 0; j < 10; j++)
				new_power = mul(new_power, power);
			power = new_power;
		}
		vector<vector<long long>> res = mul(init, finalmult);
		fout << res[0][0] << endl;
	}
	return 0;
}