Description

简要题意

给定正整数 $a,b,c$，满足 $a,b,c\textcolor{red} > 1$。对于函数 $f_k$，给出如下定义：

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

其中 $\oplus$ 表示二进制下的异或操作。

现在要求计算出 $\operatorname{lowbit}(f_{b}(a))$。其中 $\operatorname{lowbit}(x)$ 表示二进制下 $x$ 最右侧的 $1$ 所在位置对应的二进制值，例如：

$$\operatorname{lowbit}(101101\cdots 10\textcolor{red}1\underbrace{00\cdots000}_{k\text{ 个 }0})=2^k$$

特别地，若 $x=0$，则 $\operatorname{lowbit}(x)=0$。

原始题意

为了去除碎片上附加的「不明的因子」，主角组需要破开【正体不明】附加的法术。

不明的因子是一种小蛇一般的飞行物，在不同人的眼中具有不同的形象。
当有人看到它时，会按照自己的常识，把它看成自己认识的、认为合理的东西。

碎片的表面有一个由红蓝组成的长串，妖怪贤者发现，若将红看作 $0$，蓝看作 $1$，它就成了一个二进制数字 $x$。
碎片上一共有 $k$ 层不明因子，每破开一层都会使数字 $x$ 变为 $x^{2c}\oplus c$（其中 $\oplus$ 表示二进制下的异或操作）。
为了破解法术，主角组需要根据给定的常数 $c$，初始值 $a$ 和层数 $k=b$ 先破开所有的不明因子，然后计算剩下的数字所代表的串中， 最右侧的「蓝色」所在位置对应的二进制值。

经过主角们一定的分析，她们发现了 $a,b,c\textcolor{red} > 1$。

紫把式神计算机搬了出来就回去睡觉了，把编制程序的任务交给了可怜的金发小女孩。你的任务就是帮她完成程序的编制，彻底肃清异变的影响，找回丢失的记忆。

Input Format

第一行有三个正整数 $a,b,c$，含义如题面所示。

再次强调，$a,b,c\textcolor{red} > 1$。

Output Format

输出共一行一个整数，表示 $\operatorname{lowbit}(f_b(a))$ 的值。

5 2 4

1

1000000000000000000 1000000000000000000 1000000000000000000

262144

Hint

样例 1 解释

• $f_{2}(5)=f_1(5^8\oplus 4)=f_1(390{,}629)$；
• $f_1(390{,}629)=390{,}629^8\oplus 4=542{,}145{,}496{,}755{,} 385{,}548{,}075{,}315{,}235{,}215{,}044{,}149{,}100{,}456{,}165$；
• 容易发现，$f_{2}(5)$ 的 $\text{lowbit}$ 值为 $1$。

数据范围及约定

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{a,b,c\le} & \textbf{特殊性质} & \textbf{分值} \cr\hline 1 & 11 & - & 25 \cr\hline 2 & 10^{18} & \text{A} & 35 \cr\hline 3 & 10^{18} & - & 40 \cr\hline \end{array}$$

• 特殊性质 $\textbf{A}$：保证 $c$ 为偶数。

对于全部数据，保证 $1 \textcolor{red}< a,b,c\le 10^{18}$。