import java.io.FileNotFoundException; import java.io.PrintWriter; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) throws FileNotFoundException { new Main().run(); } String s = "abcdefghijklmnopqrstuvwxyz"; void run() throws FileNotFoundException { Scanner sc = new Scanner(System.in); seed = sc.nextInt(); long gt = -1, el = Integer.MAX_VALUE; while (true) { int m = (int) ((gt + el) / 2); initialize(); for (int i = 0; i < 10000001; ++i) { generate(); if (w < m) ++c1; else if (w == m) ++c2; else ++c3; } if (c1 + c2 >= 5000001) { el = m; } else { gt = m; } if (c1 + c2 >= 5000001 && c2 + c3 >= 5000001) { System.out.println(m); return; } } } long c1 = 0, c2 = 0, c3 = 0; long x = 0, y = 1, z = 2, w = 3; long seed; void initialize() { x = 0; x = seed; y = 1; z = 2; w = 3; c1 = 0; c2 = 0; c3 = 0; } long generate() { long t = (x ^ (x << 11)) & ((1L << 32) - 1); x = y & ((1L << 32) - 1); y = z & ((1L << 32) - 1); z = w & ((1L << 32) - 1); w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)) & ((1L << 32) - 1); return w; } void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }