Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

D. Crazy Decoder
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

The year is 3026, and the artificial intelligence GaLaDOS is about to take over the world. Fortunately, humanity has one last chance: it was discovered that the AI shared an administrator password with its allies. If this password is recovered, the AI can be shut down and humanity will be saved.

Of course, things will not be that easy. First, GaLaDOS defined two numbers, $$$N$$$ and $$$K$$$. Then the password $$$X$$$, initially a number between $$$0$$$ and $$$2^{32}-1$$$, went through the following encryption process $$$N$$$ times:

  1. Let $$$Y$$$ be the value of $$$X \oplus (X \cdot 2^{K})$$$.
  2. Change $$$X$$$ to be the value of the first $$$32$$$ bits of $$$Y$$$.

Here, $$$\oplus$$$ represents the XOR operation* between two numbers.

Your goal is: given $$$N$$$, $$$K$$$, and the final result of the encryption $$$S$$$, build a decoder that returns the original password $$$X$$$. If there is more than one valid password, you may return any of them.

* The XOR operation between two numbers is the result of the exclusive OR between the bits of their binary representations. For example: $$$5 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6$$$.

Input

The input is a single line containing three integers $$$N$$$ ($$$1 \leq N \leq 10^{6}$$$), $$$K$$$ ($$$1 \leq K \leq 30$$$), and $$$S$$$ ($$$1 \leq S \lt 2^{32}$$$).

Output

The output must be a single integer, the original password $$$X$$$, printed as an unsigned 32-bit integer.

Examples
Input
2 2 51
Output
3
Input
2 3 6
Output
2249744774
Input
1 1 4294967295
Output
1431655765
Note

Explanation for example 1

In this example, $$$N = 2$$$. If we start with $$$X = 3$$$, in the first step we get $$$Y = 3 \oplus (3 \cdot 2^2) = 3 \oplus 12 = 15$$$, and the value of $$$X$$$ is updated.

In the second step, we get $$$Y = 15 \oplus (15 \cdot 2^2) = 15 \oplus 60 = 51$$$. The value of $$$X$$$ is updated again, and the process ends with $$$X = 51$$$, which is the value of $$$S$$$.

Explanation for example 2

Remember that the password is a number between $$$0$$$ and $$$2^{32}-1$$$.

Explanation for example 3

Remember that $$$S$$$ is a number between $$$1$$$ and $$$2^{32}-1$$$.