Bitcoin Halving

A professor preparing an Information Security course in the Department of Big Data Information Security at Seoul Cyber University was talking with Professor Cheon about blockchain. He became curious about the mining reward of a specific block, since Bitcoin's mining reward halves each time a halving occurs.

Bitcoin's block reward is halved at regular intervals, following these rules.

• Initial reward: Starting from block $0$, the initial mining reward of each block is $R$ satoshi.
• Halving interval: Every $K$ blocks, the mining reward is halved. (Fractions are discarded when they occur, so the mining reward is always an integer.)
• Reward expiration: When the mining reward becomes smaller than $1$ satoshi, it disappears, and the mining reward of every block after that is $0$ satoshi.

For example, suppose the initial reward is $5\,000\,000\,000$ satoshi and the halving interval is $210\,000$ blocks. Then the reward for blocks $0$ through $209\,999$ is $5\,000\,000\,000$ satoshi, the reward for blocks $210\,000$ through $419\,999$ is $2\,500\,000\,000$ satoshi, $\cdots$, the reward for blocks $6\,720\,000$ through $6\,929\,999$ is $1$ satoshi, and the reward for block $6\,930\,000$ and every block after it is $0$ satoshi.

The two professors asked you to analyze this. Given the initial reward $R$, the halving interval $K$, and the number $M$ of a specific block, print the mining reward of block $M$.

The first line contains the initial reward $R$, the halving interval $K$, and the number $M$ of a specific block, in that order. $(1 \le R \le 10^{10}; 2 \le K \le 10^{10}; 0 \le M \le 10^{10})$

All numbers in the input are integers.

On the first line, print the mining reward of block $M$.