#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <math.h>
#include <cstring>

using namespace std;

#define REP(i,n)	for(int i=0;i<(n);++i)
#define REPS(i,s,t)	for(int i=(s);i<(t);++i)

#define INF 		2000000007
#define MOD			998244353

#define MAX 		100005

typedef unsigned int 			uint;
typedef unsigned long long int	ull;
typedef long long int ll;

uint x = 0, y = 1, z = 2, w = 3;
uint generate() { 
    uint t = (x^(x<<11));
    x = y;
    y = z;
    z = w;
    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); 
    return w;
}

ll quick(uint *a,ll t,ll left,ll right){
	while(left <= right){
		if(a[left] < a[t]){
			swap(a[left],a[t]);
			t = left,left++;
		}
		else if(a[right] > a[t]){
			right--;
		}
		else{
			swap(a[left],a[right]);
			swap(a[left],a[t]);
			t++,left++;
		}
	}
	return t;
}

uint a[10000001];
int main(void) {
    ll seed; cin >> seed; 
    x = seed;
    
    for (int i = 0; i < 10000001; i++) {
        a[i] = generate();
    }

	ll t=0;
	ll l=1,r=10;
	while((t=quick(a,t,l,r))!=5000000){
		if(t < 5000000){t++;l=t+1;}
		else{r=t-1;t=l,l=t+1;}
	}
	cout << a[t] << endl;//*/

    return 0;
}