x=gets.to_i
y=1
z=2
w=3
0.upto(n=1e7){t=x^x<<11&0xffffffff
x,y,z=y,z,w
w^=w>>19^t^t>>8
w<21e8?$.+=1:w<22e8&&$*<<w}
p$*.sort[n/2-$.+1]