#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

#define pf push_front
ll mod = 1004535809;

int Compare(deque<int> A, deque<int> B) {
	int NA = A.size();
	int NB = B.size();
	if (NA > NB) return 1;
	if (NA < NB) return -1;
	rep1(i, NA) {
		if (A[NA - i] > B[NB - i]) return 1;
		if (A[NA - i] < B[NB - i]) return -1;
	}
	return 0;
}

void tasu(deque<int> &A, deque<int> B) {
	int kuriage = 0;
	int NA = A.size();
	int NB = B.size();
	rep(i, NB - NA) A.pb(0);
	NA = max(NA, NB);
	rep(i, NA) {
		if (kuriage) A[i]++;
		kuriage = 0;
		if (i < NB) A[i] = A[i] + B[i];
		if (A[i] > 9) {
			A[i] -= 10;
			kuriage = 1;
		}
	}
	if (kuriage) A.pb(1);
}

void hiku(deque<int> &A, deque<int> B) {
	int kurisage = 0;
	int NA = A.size();
	int NB = B.size();
	rep(i, NA) {
		if (kurisage) A[i]--;
		kurisage = 0;
		if (i < NB) A[i] = A[i] - B[i];
		if (A[i] < 0) {
			A[i] += 10;
			kurisage = 1;
		}
	}
	while (NA > 0 && A[NA - 1] == 0) {
		NA--;
		A.pop_back();
	}
}

ll waru(deque<int> &A, ll B) {
	ll kari = 0;
	int N = A.size();
	rep1(i, N) {
		kari *= 10;
		kari += A[N - i];
		A[N - i] = kari / B;
		kari = kari % B;
	}
	rep1(i, N) {
		if (A[N - i] == 0) A.pop_back();
		else break;
	}
	return kari;
}

ll gcd(ll A, ll B) {
	if (B == 0) return A;
	return gcd(B, A % B);
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);


	string S;
	cin >> S;
	int N = S.size();

	deque<int> K, KT, tuujou, skill;
	rep(i, N) K.pf(S[i] - '0');
	KT = K;
	skill = K;
	tasu(skill, K);

	while (KT.size()) {
		tasu(tuujou, KT);
		waru(KT, 2);
	}

	hiku(skill, tuujou);
	ll kotae = waru(skill, mod);

	co(kotae);

	Would you please return 0;
}