Breaking the Spell

You are given three positive integers a, b, and c (all greater than 1). Consider the function \( f_k(x) \) defined by:

\( f_{k}(x)=\begin{cases} x^{2c} \oplus c, & k = 1\\ f_{k-1}(x^{2c} \oplus c), & k > 1 \end{cases} \)

Here, \(x^{2c}\) denotes x raised to the power of \(2c\) and \(\oplus\) represents the bitwise XOR operation. After applying the transformation for b layers (that is, computing \(f_{b}(a)\)), your task is to determine \(\operatorname{lowbit}(f_{b}(a))\).

The function \(\operatorname{lowbit}(x)\) is defined as the value of the lowest set bit in the binary representation of x. In other words, if the binary representation of x ends with k zeroes following the rightmost 1, then \(\operatorname{lowbit}(x)=2^k\). If \(x=0\), then \(\operatorname{lowbit}(x)=0\).

Background Story: An eerie spell has been cast upon an ancient relic. The spell is layered with a mysterious factor which changes the binary value inscribed on the relic. Each layer transforms the number by replacing it with \(x^{2c} \oplus c\). Once all b layers are broken, the remaining binary number hides the clue: the position of the rightmost blue (or '1') bit, whose corresponding power of 2, given by \(\operatorname{lowbit}(x)\), is the final answer.

inputFormat

The input consists of a single line with three space-separated integers: a, b, and c (each greater than 1).

outputFormat

Output the value of \(\operatorname{lowbit}(f_{b}(a))\).

sample

2 1 2

2