32952번 - 비트코인 반감기

문제

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

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

• 초기 보상: 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ドル$ 사토시이다.

수업에 들어가야 했던 노교수와 천교수는, 당신에게 분석을 의뢰했다. 초기 보상과 반감기 간격, 특정 블록 $M$의 번호가 주어지면, $M$번째 블록의 보상을 출력하자.

입력

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

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

출력

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

제한

힌트