Problem E
Drowssap

It’s a typical friday evening and Tyko is busy coding away at his dads computer. Tyko is coding all sorts of advanced programs such as machine learning algorithms, competitive programming problems and of course some nice sorting algorithm visualizers!

"Five more minutes, then you have to turn off the computer Tyko! That is enough screen time for today!", Tyko hears from the kitchen. This is bad news! Not only will Tyko not get to enjoy programming more this evening but his fans will have to wait longer before he posts another sorting algorithm compilation.

But fear not! Tyko has a plan. His dad being the tech-savvy guy he is, he has of course coded the password verification algorithm to the computer himself. Tyko has dug through all the files on the computer and found it, written below, in Python:

    def rotate(msg, amount):
        return ((msg >> amount) | (msg << (20 - amount))) & 0xfffff

    def transform(msg):
        msg = msg & 0xffffffffff
        
        a = msg & 0xfffff
        a = rotate(a, 6)
        a = a ^ 0xc21f3
        a = a | 0xaaaaa

        b = (msg >> 20) & 0xfffff
        b = b ^ a
        b = b | 0xaaaaa
        b = b ^ 0xbf83f
        b = rotate(b, 6)

        a = a ^ b

        return (a << 20) | b

If Tyko can find a password that when passed through the above transform function, produces the correct result, he can continue coding even after his dad has logged him out of the computer.

Naturally, Tyko has already figured out how to do this but he is a little busy finding a way to distract his dad from finding out that he will continue to use the computer. Perhaps you can help Tyko?

Input

A single integer $T$ ($0 \leq T < 2^{40}$).

Output

A single integer $X$ ($0 \leq X < 2^{40}$) such that $\texttt{transform}(X)=T$.

820310525263

587286992506