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 1000$

$0\le D\le 1000$

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$.