Background

The land has become muddy, and on the ground once covered by ice, everything begins to recover.
The small amount of snow covering Gensokyo seals the underground spirits that awakened this winter,
and it is also enough to make the fairies’ movements sluggish. This season of quiet sleep is about to come to an end.

The shrine maiden of Hakurei Shrine, Hakurei Reimu, heard a rumor from the magician living in the forest: someone witnessed an unbelievable ship flying in the sky through gaps in the clouds.

—The ship was empty.
The gold, silver, and treasures that were once inside have long been scattered, and what remains also gives off
a stale, moldy smell.
Even the cold spring wind is still not enough to blow the smell away.
However, the treasure left by that lord would not lose its power even if it became fragments.

It is just that those fragments are still floating around Gensokyo in strange and incomprehensible forms, adding a fog of doubt to the confusing truth.

It seems there is a deep reason. Something we do not know is brewing something.

Problem Description

Brief statement

Given positive integers $a,b,c$, satisfying $a,b,c\textcolor{red} > 1$. For the function $f_k$, it is defined as:

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

Here $\oplus$ denotes the bitwise XOR operation in binary.

Now you need to compute $\operatorname{lowbit}(f_{b}(a))$. Here $\operatorname{lowbit}(x)$ denotes the binary value corresponding to the position of the rightmost $1$ bit in $x$, for example:

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

In particular, if $x=0$, then $\operatorname{lowbit}(x)=0$.

Original statement

To remove the “unknown factor” attached to the fragments, the main characters need to break the spell cast by 【正体不明】.

The unknown factor is a flying object like a small snake, and it takes different forms in different people’s eyes.
When someone sees it, they follow their common sense and view it as something they know and consider reasonable.

On the surface of the fragment there is a long string made of red and blue. The youkai sage found that if red is treated as $0$ and blue as $1$, it becomes a binary number $x$.
There are a total of $k$ layers of unknown factors on the fragment. Each time one layer is broken, the number $x$ becomes $x^{2c}\oplus c$ (where $\oplus$ denotes bitwise XOR in binary).
To break the spell, based on the given constant $c$, initial value $a$, and number of layers $k=b$, the team must first break all unknown factors, and then compute the binary value corresponding to the position of the rightmost “blue” in the remaining string.

After some analysis, they found that $a,b,c\textcolor{red} > 1$.

Yukari brought out the 式神计算机 and went back to sleep, leaving the programming task to the poor blonde little girl. Your task is to help her finish the program, completely eliminate the incident’s influence, and recover the lost memories.

Input Format

The first line contains three positive integers $a,b,c$, with meanings as described in the statement.

Emphasized again: $a,b,c\textcolor{red} > 1$.

Output Format

Output one integer in a single line, representing the value of $\operatorname{lowbit}(f_b(a))$.

5 2 4

1

1000000000000000000 1000000000000000000 1000000000000000000

262144

Hint

Sample 1 explanation

• $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$;
• It is easy to see that the $\text{lowbit}$ value of $f_{2}(5)$ is $1$.

Constraints and notes

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{a,b,c\le} & \textbf{Special property} & \textbf{Score} \cr\hline 1 & 11 & - & 25 \cr\hline 2 & 10^{18} & \text{A} & 35 \cr\hline 3 & 10^{18} & - & 40 \cr\hline \end{array}$$

• Special property $\textbf{A}$: it is guaranteed that $c$ is even.

For all data, it is guaranteed that $1 \textcolor{red}< a,b,c\le 10^{18}$.

Translated by ChatGPT 5