题目背景

土地变得泥泞，曾被寒冰覆盖的大地上，万物开始复苏。
覆盖着幻想乡的少量积雪，封住了在这个冬天苏醒的地灵们，
也足以使妖精们的活动变得迟钝。这样安稳沉睡的季节也即将告一段落。

博丽神社的巫女博丽灵梦从居住在森林里的魔法使那儿听到了一个传闻说，有人目击到云的缝隙中有不可思议的船在空中飞行。

——船中空空如也。
曾在船中的金银财宝早已散佚，剩下的东西也散发着
陈年霉臭。
仅凭凛冽春风，仍不足以将那霉味吹散。
但是，只有那位大人留下的宝物，即使变成碎片也不会失去威力吧。

只是那些碎片依旧以不可思议不可理解的形态飘在幻想乡各处，对扑簌迷离的真相加盖了疑问的迷雾。

貌似有很深的原因。我们不知道的某种东西，在酝酿着什么。

题目描述

简要题意

给定正整数 $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$。

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

输入格式

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

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

输出格式

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

5 2 4

1

1000000000000000000 1000000000000000000 1000000000000000000

262144

提示

样例 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}$。