cheesecake is playing a mobile game where the goal is to spread a disease across the world. At any point in time, he may infect a healthy person with the pathogen, creating a patient zero. This pathogen spreads very quickly. Specifically, the number of infected people increases by a factor of ~K~ each day, with the game starting on day ~0~.

cheesecake is trying to complete a very delicate mission in which he has to infect exactly ~N~ people over a course of ~D~ days. In other words, there must be exactly ~N~ infected people on day ~D~. Help him find the minimum number of patient zeros he would have to create to complete his mission.

Constraints

For all subtasks:

~0 \le N \le 10^{18}~

~2 \le K \le 1\,000~

~0 \le D \le 1\,000~

Subtask 1 [20%]

~K = 2~

Subtask 2 [20%]

~D = 1~

Subtask 3 [60%]

No additional constraints.

Input Specification

The only line of input will have ~N~, ~K~, and ~D~, separated by spaces.

Output Specification

Output the required answer, the minimum number of patient zeros cheesecake would have to create.

Sample Input 1

8 2 1

Sample Output 1

4

Sample Input 2

9 3 2

Sample Output 2

1

Sample Input 3

10 7 10

Sample Output 3

4

Explanation for Sample Outputs

In the first case, the optimal solution is to infect ~4~ people on day ~0~.

In the second case, cheesecake should infect just one person on day ~0~. On day ~1~ there will be ~3~ people infected. And on day ~2~ there will be ~9~, as required.

In the third case, cheesecake should wait until day ~9~, infect one person, then infect ~3~ more on day ~10~.