seed = x = int(input())
y,z,w = 1,2,3

def generate():
    global x,y,z,w
    t = (x^(x<<11)) % (1<<32)
    x,y,z = y,z,w
    w = (w ^ (w>>19)) ^ (t ^ (t>>8))
    return w % (1<<32)

larger = smaller = 0
h_sh = (1<<31) + (1<<19)
l_sh = (1<<31) - (1<<19)
arr = []
for i in range(10**7+1):
    g = generate()
    if g > h_sh:
        larger += 1
    elif g < l_sh:
        smaller += 1
    else:
        arr.append(g)

n = 5*10**6
print(sorted(arr)[n-smaller])