import java.util.Scanner;

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

  private static final int N = 10000001;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int seed = sc.nextInt();
    int r = 0xffffffff;
    for(int i=31; i>=0; --i) {
      x = seed;
      y = 1;
      z = 2;
      w = 3;
      int nr = r - (1<<i);
      int cnt = 0;
      for(int k=0; k<N; ++k) {
        if(Integer.compareUnsigned(generate(), nr) <= 0) { ++cnt; }
      }
      if(cnt > N/2) { r = nr; }
    }
    System.out.println(Integer.toUnsignedLong(r));
  }
}