const MAX: u32 = u32::MAX;

struct Generator {
    x: u32,
    y: u32,
    z: u32,
    w: u32,
}

impl Generator {
    fn new(seed: u32) -> Generator {
        Generator {
            x: seed,
            y: 1,
            z: 2,
            w: 3,
        }
    }

    fn generate(&mut self) -> u32 {
        let t = (self.x ^ (self.x << 11)) & MAX;
        self.x = self.y;
        self.y = self.z;
        self.z = self.w;
        self.w = ((self.w ^ (self.w >> 19)) ^ (t ^ (t >> 8))) & MAX;
        self.w
    }
}

fn solve(n: u32, seed: u32, value: u32) -> bool {
    let mut generator = Generator::new(seed);

    let n2 = n / 2;
    let n1 = n2 + 1;

    let mut cnt = 0;
    for _ in 0..n {
        let x = generator.generate();
        if x >= value {
            cnt += 1;
        }
    }
    cnt >= n1
}

fn main() {
    use std::io;

    let mut input = String::new();
    io::stdin().read_line(&mut input).expect("Failed to read input");
    let seed: u32 = input.trim().parse().expect("Input is not a valid u32");

    let n: u32 = 10_000_001;

    let mut low: u32 = 1 << 2 - 1;
    let mut high: u32 = 0;
    for i in 0..31 {
        high += 1 << i;
    }

    while high - low > 1 {
        let mid = (high + low) >> 1;
        if solve(n, seed, mid) {
            low = mid;
        } else {
            high = mid;
        }
    }

    if solve(n, seed, high) {
        println!("{}", high);
    } else {
        println!("{}", low);
    }
}