import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

seed = int(read())

def f(seed,pivot):
    x,y,z,w = seed,1,2,3
    cnt = 0
    max_w = 0
    mask = (1 << 32) - 1
    for _ in range(10 ** 7 + 1):
        t = x^((x<<11)&mask)
        x = y; y = z; z = w
        w = (w^(w>>19)) ^ (t^(t>>8))
        if w <= pivot:
            if max_w < w:
                max_w = w
            cnt += 1
    return cnt - 5000001, max_w

left = 0; fl = -500001
right = 1 << 32; fr = 500000
while True:
    x = int(left + (right - left) * (-fl) / (fr - fl)) + 1
    fx, w = f(seed,x)
    if fx == 0:
        answer = w
        break
    if fx > 0:
        right = w; fr = fx
    else:
        left = x; fl = fx
print(answer)