비트코인 반감기

서울사이버대학교 빅데이터 정보보호학과에서 정보보호개론 수업을 준비하던 노교수는 블록체인에 대해 천교수와 이야기하다가, 반감기가 지날 때마다 절반으로 줄어드는 비트코인 채굴 보상에서 특정 블록의 채굴 보상이 얼마인지 궁금해졌다.

비트코인은 일정한 간격으로 블록의 채굴 보상이 절반으로 줄어들며, 다음 규칙을 따른다.

• 초기 보상: $0$번 블록부터 시작하며, 각 블록의 초기 채굴 보상은 $R$ 사토시이다.
• 반감기 간격: 매 $K$ 블록마다 채굴 보상이 절반으로 줄어든다. (소수점이 생기면 버린다. 즉, 채굴 보상은 항상 정수이다.)
• 보상 소멸: 채굴 보상이 $1$ 사토시보다 작아지면 사라지며, 이후 모든 블록의 채굴 보상은 $0$ 사토시가 된다.

예를 들어, 초기 보상이 $5\,000\,000\,000$ 사토시이고 반감기 간격이 $210\,000$ 블록이라면, $0$번 블록부터 $209\,999$번 블록까지의 보상은 $5\,000\,000\,000$ 사토시, $210\,000$번 블록부터 $419\,999$번 블록까지의 보상은 $2\,500\,000\,000$ 사토시, $\cdots$, $6\,720\,000$번 블록부터 $6\,929\,999$번 블록까지의 보상은 $1$ 사토시, $6\,930\,000$번 블록부터 이후 모든 블록의 보상은 $0$ 사토시이다.

두 교수는 당신에게 분석을 의뢰했다. 초기 보상 $R$, 반감기 간격 $K$, 특정 블록의 번호 $M$이 주어지면, $M$번째 블록의 채굴 보상을 구하라.

첫 번째 줄에 초기 보상 $R$, 반감기 간격 $K$, 특정 블록의 번호 $M$이 차례대로 주어진다. $(1 \le R \le 10^{10}; 2 \le K \le 10^{10}; 0 \le M \le 10^{10})$

입력으로 주어지는 모든 수는 정수이다.

첫 번째 줄에 $M$번째 블록의 채굴 보상을 출력한다.