#include <bits/stdc++.h>
using namespace std;
using u32 = uint32_t;
using u64 = uint64_t;
const int N = 1e7+1;
u32 x = 0, y = 1, z = 2, w = 3;
u32 generate() {
    u32 t = (x^(x<<11));
    x = y;
    y = z;
    z = w;
    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    return w;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	u64 seed;
	cin >> seed;
	u32 lo = 0, hi = -1;
	while(hi - lo > 1) {
		u32 mi = lo + (hi - lo) / 2;
		int t = 0;
		x = seed, y = 1, z = 2, w = 3;
		for(int i = 0; i < N; i++) {
			u32 s = generate();
			if(s < mi) {
				t += 1;
			}
		}
		if(t < N/2 + 1) lo = mi;
		else hi = mi;
	}
	cout << lo << endl;
}